Minimum Adjacent Swaps to Sort

Given a permutation of the integers from 1 to (n), compute the minimum number of adjacent swaps required to sort the array in ascending order.

This problem is equivalent to counting the number of inversions in the permutation. An inversion is a pair ((i,j)) such that (i < j) and (a_i > a_j).

Efficient solutions use data structures such as the Fenwick Tree (or Binary Indexed Tree) to obtain the answer in (O(n\log n)) time. Your task is to implement such an algorithm that reads from standard input and writes the result to standard output.

inputFormat

The first line contains a single integer (n) ((1 \le n \le 10^5)), representing the size of the permutation. The second line contains (n) space-separated integers which form a permutation of the integers from 1 to (n).

outputFormat

Output a single integer on a line by itself — the minimum number of adjacent swaps required to sort the permutation.## sample

3
3 1 2

2