Comptage d’inversions
Il était une fois, dans un royaume mystérieux, un sage sorcier nommé Merlin. Merlin avait le pouvoir exceptionnel de déceler les schémas cachés dans les permutations. Il portait un intérêt tout particulier au concept d’inversions dans une permutation.
Une inversion dans une permutation est une paire d’éléments
($$a_i, a_j$$) telle que i < j et . Le nombre total d’inversions dans une permutation indique à quel point cette permutation s’éloigne de l’ordre croissant.Merlin mit au défi les talentueux programmeurs avec le problème suivant : Étant donné une permutation d’entiers allant de
1 à n, votre tâche consiste à calculer le nombre d’inversions présentes dans cette permutation.Entrée
La première ligne contient un seul entier
n (1 ≤ n ≤ 100 000), qui représente la taille de la permutation. La deuxième ligne contient n entiers séparés par des espaces, représentant les éléments de la permutation.Sortie
Affichez un seul entier, indiquant le nombre d’inversions dans la permutation donnée.
Exemples
Entrée | Sortie |
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