Inversionsanzahl
Es war einmal in einem mystischen Land, da lebte ein weiser Zauberer namens Merlin. Merlin verfügte über eine einzigartige Gabe, verborgene Muster in Permutationen zu erkennen. Besonders fasziniert war er vom Konzept der Inversionen in einer Permutation.
Eine Inversion in einer Permutation ist ein Paar von Elementen (), bei dem
i < j und gilt. Die Anzahl solcher Inversionen zeigt, wie weit die Permutation von einer aufsteigend sortierten Reihenfolge abweicht.Um die Fähigkeiten der talentierten Programmierer zu prüfen, stellte Merlin folgende Aufgabe: Gegeben ist eine Permutation der ganzen Zahlen von
1 bis n. Bestimmen Sie die Anzahl der Inversionen in dieser Permutation.Input
Die erste Zeile enthält eine einzelne ganze Zahl
n (1 ≤ n ≤ 100 000), welche die Größe der Permutation angibt. In der zweiten Zeile stehen n durch Leerzeichen getrennte ganze Zahlen, die die Elemente der Permutation darstellen.Output
Geben Sie eine einzelne ganze Zahl aus, welche die Anzahl der Inversionen in der gegebenen Permutation angibt.
Beispiele
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