#include <bits/stdc++.h>
using namespace std;
const unsigned long long MN = 1e6 + 7;
long long lazy[MN * 4], lazy2[MN * 4];
void push(unsigned long long v, unsigned long long l, unsigned long long r) {
  lazy[(v << 1)] = lazy[(v << 1)] + lazy[v];
  lazy[((v << 1) | 1)] = lazy[((v << 1) | 1)] + lazy[v];
  lazy[v] = 0;
}
void push2(unsigned long long v, unsigned long long l, unsigned long long r) {
  lazy2[(v << 1)] = lazy2[(v << 1)] + lazy2[v];
  lazy2[((v << 1) | 1)] = lazy2[((v << 1) | 1)] + lazy2[v];
  lazy2[v] = 0;
}
void upd(unsigned long long v, unsigned long long l, unsigned long long r,
         unsigned long long p, unsigned long long q) {
  if (l == p && r == q) {
    lazy[v]++;
    return;
  }
  push(v, l, r);
  if (p <= ((l + r) >> 1))
    upd((v << 1), l, ((l + r) >> 1), p, min(((l + r) >> 1), q));
  if (q > ((l + r) >> 1))
    upd(((v << 1) | 1), ((l + r) >> 1) + 1, r, max(((l + r) >> 1) + 1, p), q);
}
void upd2(unsigned long long v, unsigned long long l, unsigned long long r,
          unsigned long long p, unsigned long long q, unsigned long long vl) {
  if (vl == 0) return;
  if (l == p && r == q) {
    lazy2[v] += vl;
    return;
  }
  push2(v, l, r);
  if (p <= ((l + r) >> 1))
    upd2((v << 1), l, ((l + r) >> 1), p, min(((l + r) >> 1), q), vl);
  if (q > ((l + r) >> 1))
    upd2(((v << 1) | 1), ((l + r) >> 1) + 1, r, max(((l + r) >> 1) + 1, p), q,
         vl);
}
unsigned long long ask(unsigned long long v, unsigned long long l,
                       unsigned long long r, unsigned long long po) {
  if (l == r) {
    return lazy[v];
  }
  push(v, l, r);
  unsigned long long re = 0;
  if (po <= ((l + r) >> 1))
    re += ask((v << 1), l, ((l + r) >> 1), po);
  else
    re += ask(((v << 1) | 1), ((l + r) >> 1) + 1, r, po);
  return re;
}
unsigned long long ask2(unsigned long long v, unsigned long long l,
                        unsigned long long r, unsigned long long po) {
  if (l == r) {
    return lazy2[v];
  }
  push2(v, l, r);
  unsigned long long re = 0;
  if (po <= ((l + r) >> 1))
    re += ask2((v << 1), l, ((l + r) >> 1), po);
  else
    re += ask2(((v << 1) | 1), ((l + r) >> 1) + 1, r, po);
  return re;
}
unsigned long long a[MN];
vector<pair<unsigned long long, unsigned long long> > v;
signed main() {
  ios::sync_with_stdio(false);
  cin.tie();
  unsigned long long n;
  cin >> n;
  for (unsigned long long i = 0; i < n; i++) {
    cin >> a[i];
    v.push_back({a[i], i});
  }
  sort(v.begin(), v.end());
  for (unsigned long long i = 0; i < n; i++) {
    a[v[i].second] = i + 1;
  }
  unsigned long long ans = 0;
  for (unsigned long long i = 0; i < n; i++) {
    ans += ask2(1, 0, n + 20, a[i]);
    upd2(1, 0, n + 20, 0, a[i] - 1, ask(1, 0, n + 20, a[i]));
    upd(1, 0, n + 20, 0, a[i] - 1);
  }
  cout << ans << '\n';
}

### Prompt

Please provide a cpp coded solution 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;
const unsigned long long MN = 1e6 + 7;
long long lazy[MN * 4], lazy2[MN * 4];
void push(unsigned long long v, unsigned long long l, unsigned long long r) {
  lazy[(v << 1)] = lazy[(v << 1)] + lazy[v];
  lazy[((v << 1) | 1)] = lazy[((v << 1) | 1)] + lazy[v];
  lazy[v] = 0;
}
void push2(unsigned long long v, unsigned long long l, unsigned long long r) {
  lazy2[(v << 1)] = lazy2[(v << 1)] + lazy2[v];
  lazy2[((v << 1) | 1)] = lazy2[((v << 1) | 1)] + lazy2[v];
  lazy2[v] = 0;
}
void upd(unsigned long long v, unsigned long long l, unsigned long long r,
         unsigned long long p, unsigned long long q) {
  if (l == p && r == q) {
    lazy[v]++;
    return;
  }
  push(v, l, r);
  if (p <= ((l + r) >> 1))
    upd((v << 1), l, ((l + r) >> 1), p, min(((l + r) >> 1), q));
  if (q > ((l + r) >> 1))
    upd(((v << 1) | 1), ((l + r) >> 1) + 1, r, max(((l + r) >> 1) + 1, p), q);
}
void upd2(unsigned long long v, unsigned long long l, unsigned long long r,
          unsigned long long p, unsigned long long q, unsigned long long vl) {
  if (vl == 0) return;
  if (l == p && r == q) {
    lazy2[v] += vl;
    return;
  }
  push2(v, l, r);
  if (p <= ((l + r) >> 1))
    upd2((v << 1), l, ((l + r) >> 1), p, min(((l + r) >> 1), q), vl);
  if (q > ((l + r) >> 1))
    upd2(((v << 1) | 1), ((l + r) >> 1) + 1, r, max(((l + r) >> 1) + 1, p), q,
         vl);
}
unsigned long long ask(unsigned long long v, unsigned long long l,
                       unsigned long long r, unsigned long long po) {
  if (l == r) {
    return lazy[v];
  }
  push(v, l, r);
  unsigned long long re = 0;
  if (po <= ((l + r) >> 1))
    re += ask((v << 1), l, ((l + r) >> 1), po);
  else
    re += ask(((v << 1) | 1), ((l + r) >> 1) + 1, r, po);
  return re;
}
unsigned long long ask2(unsigned long long v, unsigned long long l,
                        unsigned long long r, unsigned long long po) {
  if (l == r) {
    return lazy2[v];
  }
  push2(v, l, r);
  unsigned long long re = 0;
  if (po <= ((l + r) >> 1))
    re += ask2((v << 1), l, ((l + r) >> 1), po);
  else
    re += ask2(((v << 1) | 1), ((l + r) >> 1) + 1, r, po);
  return re;
}
unsigned long long a[MN];
vector<pair<unsigned long long, unsigned long long> > v;
signed main() {
  ios::sync_with_stdio(false);
  cin.tie();
  unsigned long long n;
  cin >> n;
  for (unsigned long long i = 0; i < n; i++) {
    cin >> a[i];
    v.push_back({a[i], i});
  }
  sort(v.begin(), v.end());
  for (unsigned long long i = 0; i < n; i++) {
    a[v[i].second] = i + 1;
  }
  unsigned long long ans = 0;
  for (unsigned long long i = 0; i < n; i++) {
    ans += ask2(1, 0, n + 20, a[i]);
    upd2(1, 0, n + 20, 0, a[i] - 1, ask(1, 0, n + 20, a[i]));
    upd(1, 0, n + 20, 0, a[i] - 1);
  }
  cout << ans << '\n';
}

```