#include <bits/stdc++.h>
using namespace std;
bool sortbysec(const pair<long long, long long>& a,
               const pair<long long, long long>& b) {
  return (a.second < b.second);
}
vector<int> merge(vector<int>& v1, vector<int>& v2) {
  int i = 0, j = 0;
  vector<int> v;
  while (i < v1.size() && j < v2.size()) {
    if (v1[i] <= v2[j]) {
      v.push_back(v1[i]);
      i++;
    } else {
      v.push_back(v2[j]);
      j++;
    }
  }
  for (int k = i; k < v1.size(); k++) v.push_back(v1[k]);
  for (int k = j; k < v2.size(); k++) v.push_back(v2[k]);
  return v;
}
void buildTree(vector<int>* tree, int* arr, int index, int s, int endl) {
  if (s == endl) {
    tree[index].push_back(arr[s]);
    return;
  }
  int mid = (s + endl) / 2;
  buildTree(tree, arr, 2 * index, s, mid);
  buildTree(tree, arr, 2 * index + 1, mid + 1, endl);
  tree[index] = merge(tree[2 * index], tree[2 * index + 1]);
}
int query(vector<int>* tree, int index, int s, int endl, int l, int r, int k) {
  if (r < s || l > endl) return 0;
  if (s >= l && endl <= r) {
    return (tree[index].size() -
            (lower_bound(tree[index].begin(), tree[index].end(), k) -
             tree[index].begin()));
  }
  int mid = (s + endl) / 2;
  return (query(tree, 2 * index, s, mid, l, r, k) +
          query(tree, 2 * index + 1, mid + 1, endl, l, r, k));
}
void solve() {
  int n;
  cin >> n;
  int a[n];
  for (int i = 0; i < n; i++) cin >> a[i];
  vector<int> tree[4 * n + 1];
  buildTree(tree, a, 1, 0, n - 1);
  long long count = 0;
  for (long long i = 1; i < n - 1; i++) {
    long long x = query(tree, 1, 0, n - 1, 0, i - 1, a[i]);
    long long y = n - i - 1 - query(tree, 1, 0, n - 1, i + 1, n - 1, a[i]);
    count += x * y;
  }
  cout << count << endl;
}
int main() { solve(); }

### Prompt

Develop a solution in CPP to the problem described below:

The Romans have attacked again. This time they are much more than the Persians but Shapur is ready to defeat them. He says: "A lion is never afraid of a hundred sheep". 

Nevertheless Shapur has to find weaknesses in the Roman army to defeat them. So he gives the army a weakness number.

In Shapur's opinion the weakness of an army is equal to the number of triplets i, j, k such that i < j < k and ai > aj > ak where ax is the power of man standing at position x. The Roman army has one special trait — powers of all the people in it are distinct.

Help Shapur find out how weak the Romans are.

Input

The first line of input contains a single number n (3 ≤ n ≤ 106) — the number of men in Roman army. Next line contains n different positive integers ai (1 ≤ i ≤ n, 1 ≤ ai ≤ 109) — powers of men in the Roman army. 

Output

A single integer number, the weakness of the Roman army. 

Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preffered to use cout (also you may use %I64d).

Examples

Input

3
3 2 1


Output

1


Input

3
2 3 1


Output

0


Input

4
10 8 3 1


Output

4


Input

4
1 5 4 3


Output

1

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
bool sortbysec(const pair<long long, long long>& a,
               const pair<long long, long long>& b) {
  return (a.second < b.second);
}
vector<int> merge(vector<int>& v1, vector<int>& v2) {
  int i = 0, j = 0;
  vector<int> v;
  while (i < v1.size() && j < v2.size()) {
    if (v1[i] <= v2[j]) {
      v.push_back(v1[i]);
      i++;
    } else {
      v.push_back(v2[j]);
      j++;
    }
  }
  for (int k = i; k < v1.size(); k++) v.push_back(v1[k]);
  for (int k = j; k < v2.size(); k++) v.push_back(v2[k]);
  return v;
}
void buildTree(vector<int>* tree, int* arr, int index, int s, int endl) {
  if (s == endl) {
    tree[index].push_back(arr[s]);
    return;
  }
  int mid = (s + endl) / 2;
  buildTree(tree, arr, 2 * index, s, mid);
  buildTree(tree, arr, 2 * index + 1, mid + 1, endl);
  tree[index] = merge(tree[2 * index], tree[2 * index + 1]);
}
int query(vector<int>* tree, int index, int s, int endl, int l, int r, int k) {
  if (r < s || l > endl) return 0;
  if (s >= l && endl <= r) {
    return (tree[index].size() -
            (lower_bound(tree[index].begin(), tree[index].end(), k) -
             tree[index].begin()));
  }
  int mid = (s + endl) / 2;
  return (query(tree, 2 * index, s, mid, l, r, k) +
          query(tree, 2 * index + 1, mid + 1, endl, l, r, k));
}
void solve() {
  int n;
  cin >> n;
  int a[n];
  for (int i = 0; i < n; i++) cin >> a[i];
  vector<int> tree[4 * n + 1];
  buildTree(tree, a, 1, 0, n - 1);
  long long count = 0;
  for (long long i = 1; i < n - 1; i++) {
    long long x = query(tree, 1, 0, n - 1, 0, i - 1, a[i]);
    long long y = n - i - 1 - query(tree, 1, 0, n - 1, i + 1, n - 1, a[i]);
    count += x * y;
  }
  cout << count << endl;
}
int main() { solve(); }

```