A row of n crates must be sorted by color rank into non-decreasing order, but the only allowed operation is swapping two crates that sit next to each other. Report the minimum number of such adjacent swaps needed to sort the row.
Input format
Line 1: an integer n.
Line 2: n space-separated integers, the color ranks in row order.
Output format
A single integer: the minimum number of adjacent swaps to sort the row into non-decreasing order.
Constraints
- 1 ≤ n ≤ 100000
- -1000000000 ≤ each color rank ≤ 1000000000