Inversion Count
C’era una volta, in una terra mistica, un saggio stregone di nome Merlino. Merlino possedeva un dono unico: riusciva a distinguere i pattern nascosti nelle permutazioni. Era particolarmente affascinato dal concetto di inversione all’interno di una permutazione.
Un’inversione in una permutazione consiste in una coppia di elementi
($a_i, a_j$) per cui i < j e . Il numero totale di inversioni rappresenta quanto la permutazione si discosta dall’essere ordinata in modo crescente.Merlino decise di mettere alla prova i programmatori più talentuosi con un problema ben preciso: data una permutazione di interi compresi tra
1 e n, bisogna calcolare il numero di inversioni che contiene.Input
La prima riga contiene un singolo intero
n (1 ≤ n ≤ 100 000), che indica la dimensione della permutazione. La seconda riga contiene n numeri interi separati da spazi, corrispondenti agli elementi della permutazione.Output
Stampa un solo intero, corrispondente al numero di inversioni presenti nella permutazione fornita.
Esempi
Input | Output |
5
3 1 4 2 5 | 3 |
4
1 2 3 4 | 0 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB