/*
Given an array A: 1 6 7 5 2 4 3
The task is to compute the number of inversions.
*/


// Naive solution: O(n²)
int number_of_inversions(vector<int> A) {
  int n = A.size();
  int inv = 1;
  for (int i = 0 ; i < n ; ++i)
    for (int j = i+1 ; j < n ; ++j)
       inv ^= (A[i] > A[j]);
  return inv;
}



// Optimised: O (n log n): using fenwick tree

int *tree = NULL;
int n;

void update(int i, int value){
  while(i<=n){
    tree[i]+=value;
    i+=(i&-i);
  }
}

int sum(int i){
  int sm=0;
  while(i>0){
    sm+=tree[i];
    i-=(i&-i);
  }
  return sm;
}

int range_sum(int i, int j){
  return sum(j)-sum(i);
}


int number_of_inversions(vector<int> A) {
  int n = A.size();
  tree = new int[n+1];
   fill_n(tree, n+1, 0);
   int inv = 0;
   for (int i = 0; i < n; ++i) {
         inv += range_sum(A[i], n);
         update(A[i], 1);
   }
  return inv;
}