// できること
// 一点追加
// 範囲和
// ei1333's BIT
struct BIT {
  VI data;

  BIT(ll sz) {
    data.assign(++sz, 0);
  }

  // sum of [0,k]
  ll sum(ll k) {
    ll ret = 0;
    for(++k; k > 0; k -= k & -k) ret += data[k];
    return (ret);
  }

  // [i, j]
  ll range_sum(ll i, ll j){
    if(i==0){
      return sum(j);
    }else{
      return sum(j) - sum(i-1);    
    }
  }

  void add(ll k, ll x) {
    for(++k; k < SZ(data); k += k & -k) data[k] += x;
  }
};

// BITを用いた転倒数
// 
// (Aの値域に注意, 必要なら座標圧縮する)
// 入力：{100,100}などはREします
// ... というのはBITの値域が0~N-1なため。BIT(N)のNを直接指定するならRE回避可能
ll inversion_number(VI A){
  ll N = A.size();
  auto bit = BIT(N);
  ll cnt = 0;
  FOR(i, 0, N){
      ll a = A[i];
      assert(a<N);
      assert(a>=0);
      ll num = i - bit.sum(a); // aより先に出現した、aよりも大きい数の個数
                               // a以下の数をスルーするためにbit.sum(a)で引いている
      cnt += num;
      bit.add(a, 1);
  }
  return cnt;
}