Online Programming Server

Do you remember how bubble sort works? It swaps adjacent elements if they are not in the correct order. Given an array A, Alice is interested in how many swaps the bubble sort algorithm will perform.

This is equivalent to counting how many pairs of (i, j) satisfy i < j and A[i] > A[j], namely a inversion. The inversion number of an array is the number of inversions. Your task is compute this number.

The first line contains an integer N (1 ≤ N ≤ 100000), the length of the array.
The second line contain N integers representing the array. (0 ≤ A_i ≤ 10⁹)

The inversion number of array A.