#include <iostream>
#include <vector>
#include <stack>
#include <cmath>
using namespace std;

int n, a[500000];
long long ans = 0;

void func(int l, int r){
  if(l + 1 >= r) return;
  int m = (l + r) / 2;
  func(l, m);
  int t1[m - l + 1], t2[r - m + 1];
  for(int i = l; i < m; i++){
    t1[i - l] = a[i];
  }
  t1[m - l] = 1000000001;
  func(m, r);
  for(int i = m; i < r; i++){
    t2[i - m] = a[i];
  }
  t2[r - m] = 1000000001;
  int t1i = 0, t2i = 0;
  for(int i = l; i < r; i++){
    if(t1[t1i] <= t2[t2i]) a[i] = t1[t1i++];
    else{
      a[i] = t2[t2i++];
      ans += (m + t2i - 1) - i;
    }
  }
  return;
}

void solve(){
  cin >> n;
  for(int i = 0; i < n; i++) cin >> a[i];
  func(0, n);
  cout << ans << endl;
  return;
}

int main(){
  solve();
  return 0;
}


### Prompt

Please formulate a Cpp solution to the following problem:

For a given sequence $A = \\{a_0, a_1, ... a_{n-1}\\}$, the number of pairs $(i, j)$ where $a_i > a_j$ and $i < j$, is called the number of inversions. The number of inversions is equal to the number of swaps of Bubble Sort defined in the following program:


bubbleSort(A)
cnt = 0 // the number of inversions
for i = 0 to A.length-1
for j = A.length-1 downto i+1
if A[j] < A[j-1]
	swap(A[j], A[j-1])
	cnt++

return cnt


For the given sequence $A$, print the number of inversions of $A$. Note that you should not use the above program, which brings Time Limit Exceeded.

Constraints

* $ 1 \leq n \leq 200,000$
* $ 0 \leq a_i \leq 10^9$
* $a_i$ are all different

Input

In the first line, an integer $n$, the number of elements in $A$, is given. In the second line, the elements $a_i$ ($i = 0, 1, .. n-1$) are given separated by space characters.

Examples

Input

5
3 5 2 1 4


Output

6


Input

3
3 1 2


Output

2

### Response

```cpp
#include <iostream>
#include <vector>
#include <stack>
#include <cmath>
using namespace std;

int n, a[500000];
long long ans = 0;

void func(int l, int r){
  if(l + 1 >= r) return;
  int m = (l + r) / 2;
  func(l, m);
  int t1[m - l + 1], t2[r - m + 1];
  for(int i = l; i < m; i++){
    t1[i - l] = a[i];
  }
  t1[m - l] = 1000000001;
  func(m, r);
  for(int i = m; i < r; i++){
    t2[i - m] = a[i];
  }
  t2[r - m] = 1000000001;
  int t1i = 0, t2i = 0;
  for(int i = l; i < r; i++){
    if(t1[t1i] <= t2[t2i]) a[i] = t1[t1i++];
    else{
      a[i] = t2[t2i++];
      ans += (m + t2i - 1) - i;
    }
  }
  return;
}

void solve(){
  cin >> n;
  for(int i = 0; i < n; i++) cin >> a[i];
  func(0, n);
  cout << ans << endl;
  return;
}

int main(){
  solve();
  return 0;
}


```