#include <bits/stdc++.h>
using namespace std;
struct num {
  long long val;
  int pl;
  num(){};
  num(long long const& v, int const& p) {
    val = v;
    pl = p;
  }
};
long long tree[4000008][2];
num a[1000002];
long long o = 1;
long long const INF = 1e18;
void build(int const& n) {
  while (o < n) o *= 2;
  return;
}
long long getsum(int const& v, int const& lv, int const& rv, int const& l,
                 int const& r, int const& d) {
  if (rv < l || r < lv) return 0;
  if (l <= lv && rv <= r) return tree[v][d];
  int mv = (lv + rv) / 2;
  long long temp =
      getsum(2 * v, lv, mv, l, r, d) + getsum(2 * v + 1, mv + 1, rv, l, r, d);
  return temp;
}
void rewr(int id, int const& d, long long const& val) {
  id += o;
  tree[id][d] = val;
  id /= 2;
  while (id >= 1) {
    tree[id][d] = tree[2 * id][d] + tree[2 * id + 1][d];
    id /= 2;
  }
  return;
}
bool asort(num const& x, num const& y) { return x.val > y.val; }
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%I64d", &a[i].val);
    a[i].pl = i;
  }
  build(n);
  sort(a, a + n, asort);
  long long ans = 0;
  for (int i = 0; i < n; i++) {
    int t = getsum(1, 1, o, 1, a[i].pl, 0);
    rewr(a[i].pl, 0, 1);
    rewr(a[i].pl, 1, t);
    ans += getsum(1, 1, o, 1, a[i].pl, 1);
  }
  printf("%I64d", ans);
  return 0;
}

### Prompt

Please create a solution in cpp to the following problem:

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;
struct num {
  long long val;
  int pl;
  num(){};
  num(long long const& v, int const& p) {
    val = v;
    pl = p;
  }
};
long long tree[4000008][2];
num a[1000002];
long long o = 1;
long long const INF = 1e18;
void build(int const& n) {
  while (o < n) o *= 2;
  return;
}
long long getsum(int const& v, int const& lv, int const& rv, int const& l,
                 int const& r, int const& d) {
  if (rv < l || r < lv) return 0;
  if (l <= lv && rv <= r) return tree[v][d];
  int mv = (lv + rv) / 2;
  long long temp =
      getsum(2 * v, lv, mv, l, r, d) + getsum(2 * v + 1, mv + 1, rv, l, r, d);
  return temp;
}
void rewr(int id, int const& d, long long const& val) {
  id += o;
  tree[id][d] = val;
  id /= 2;
  while (id >= 1) {
    tree[id][d] = tree[2 * id][d] + tree[2 * id + 1][d];
    id /= 2;
  }
  return;
}
bool asort(num const& x, num const& y) { return x.val > y.val; }
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%I64d", &a[i].val);
    a[i].pl = i;
  }
  build(n);
  sort(a, a + n, asort);
  long long ans = 0;
  for (int i = 0; i < n; i++) {
    int t = getsum(1, 1, o, 1, a[i].pl, 0);
    rewr(a[i].pl, 0, 1);
    rewr(a[i].pl, 1, t);
    ans += getsum(1, 1, o, 1, a[i].pl, 1);
  }
  printf("%I64d", ans);
  return 0;
}

```