Two judges ranked the same items, and the second judge's ordering is described by a sequence of n rating values. The disagreement between the judges is measured by the number of inversions: the count of index pairs (i, j) with i < j but value[i] > value[j]. Report that count. Values may repeat; a tie (value[i] == value[j]) is NOT an inversion.
Input format
Line 1: an integer n.
Line 2: n space-separated integers, the rating values.
Output format
A single integer: the number of inversions.
Constraints
- 1 ≤ n ≤ 100000
- -1000000000 ≤ value ≤ 1000000000