Inversion Count
Once upon a time in a mystical land, there lived a wise sorcerer named Merlin. Merlin possessed a unique power to perceive the hidden patterns in permutations. He was particularly intrigued by the concept of inversions in a permutation.
An inversion in a permutation is a pair of elements
() such that i < j and Merlin decided to challenge the talented programmers by posing the following problem: Given a permutation of integers from
1 to n, your task is to calculate the number of inversions present in the permutation.Input
The first line contains a single integer
n (1 ≤ n ≤ 100 000), representing the size of the permutation. The second line contains n space-separated integers, representing the elements of the permutation.Output
Print a single integer, representing the number of inversions in the given permutation.
Examples
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