# SGU 180 - Inversions

## Description

There are $N$ integers ($1\leq N\leq 65537$) $A_1, A_2,\cdots, A_N$ ($0\leq A_i\leq 10^9$). You need to find amount of such pairs $(i, j)$ that $1\leq i < j\leq N$ and $A[i]>A[j]$.

## Input

The first line of the input contains the number $N$. The second line contains $N$ numbers $A_1,\cdots,A_N$.

## Output

Write amount of such pairs.

## Sample Input

 1 2  5 2 3 1 5 4 

## Sample Output

 1  3 

## Solution

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61  #include #include #include using namespace std; const int MAX = 102400; int N; int T[MAX], A[MAX], B[MAX]; int LowBit(int x); void Update(int x, int y); long long Sum(int x); int main() { while(cin >> N) { long long ans = 0; memset(T, 0, sizeof(T)); for(int i = 1; i <= N; i++) { cin >> A[i]; B[i] = A[i]; } sort(B + 1, B + N + 1); for(int i = 1; i <= N; i++) { A[i] = lower_bound(B + 1, B + N + 1, A[i]) - B; } for(int i = 1; i <= N; i++) { Update(A[i], 1); ans += A[i] - Sum(A[i] - 1) - 1; } cout << ans << endl; } return 0; } int LowBit(int x) { return x & (-x); } void Update(int x, int y) { while(x <= N) { T[x] += y; x += LowBit(x); } } long long Sum(int x) { long long ans = 0; while(x) { ans += T[x]; x -= LowBit(x); } return ans; }