#include <bits/stdc++.h>
using namespace std;
int SET(int n, int pos) { return n = n | (1 << pos); }
int RESET(int n, int pos) { return n = n & ~(1 << pos); }
int CHECK(int n, int pos) { return (bool)(n & (1 << pos)); }
int str2int(string s) {
  stringstream ss(s);
  int x;
  ss >> x;
  return x;
}
string int2str(int a) {
  stringstream ss;
  ss << a;
  string str = ss.str();
  return str;
}
string char2str(char a) {
  stringstream ss;
  ss << a;
  string str = ss.str();
  return str;
}
long long int bigMod(long long int n, long long int power, long long int MOD) {
  if (power == 0) return 1;
  if (power % 2 == 0) {
    long long int ret = bigMod(n, power / 2, MOD);
    return ((ret % MOD) * (ret % MOD)) % MOD;
  } else
    return ((n % MOD) * (bigMod(n, power - 1, MOD) % MOD)) % MOD;
}
long long int modInverse(long long int a, long long int m) {
  long long int m0 = m, t, q;
  long long int x0 = 0, x1 = 1;
  if (m == 1) return 0;
  while (a > 1) {
    q = a / m;
    t = m;
    m = a % m, a = t;
    t = x0;
    x0 = x1 - q * x0;
    x1 = t;
  }
  if (x1 < 0) x1 += m0;
  return x1;
}
int POW(int x, int y) {
  int res = 1;
  for (; y;) {
    if ((y & 1)) {
      res *= x;
    }
    x *= x;
    y >>= 1;
  }
  return res;
}
int inverse(int x) {
  double p = ((double)1.0) / x;
  return (p) + 1e-9;
}
int gcd(int a, int b) {
  while (b) b ^= a ^= b ^= a %= b;
  return a;
}
int nC2(int n) { return n * (n - 1) / 2; }
long long int MOD(long long int n, long long int mod) {
  if (n >= 0)
    return n % mod;
  else if (-n == mod)
    return 0;
  else
    return mod + (n % mod);
}
long long int tree[1000005], temp[1000005];
int n, val[1000005];
vector<pair<int, int> > data;
void update(int i, long long int val) {
  while (i < 1000005) {
    tree[i] += val;
    i += i & (-i);
  }
}
long long int query(int i) {
  long long int sum = 0;
  while (i > 0) {
    sum += tree[i];
    i -= i & (-i);
  }
  return sum;
}
int main() {
  int t, cas = 0;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    int p;
    scanf("%d", &p);
    data.push_back(make_pair(p, i));
  }
  sort(data.begin(), data.end());
  int cnt = 0;
  for (int i = 0; i < data.size(); i++) {
    if (i > 0 && data[i].first == data[i - 1].first) {
      val[data[i].second] = cnt;
      continue;
    }
    val[data[i].second] = ++cnt;
  }
  for (int i = n; i >= 1; i--) {
    temp[i] = query(val[i] - 1);
    update(val[i], 1);
  }
  long long int ans = 0;
  memset(tree, 0, sizeof(tree));
  for (int i = n; i >= 1; i--) {
    ans += query(val[i] - 1);
    update(val[i], temp[i]);
  }
  printf("%lld\n", 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;
int SET(int n, int pos) { return n = n | (1 << pos); }
int RESET(int n, int pos) { return n = n & ~(1 << pos); }
int CHECK(int n, int pos) { return (bool)(n & (1 << pos)); }
int str2int(string s) {
  stringstream ss(s);
  int x;
  ss >> x;
  return x;
}
string int2str(int a) {
  stringstream ss;
  ss << a;
  string str = ss.str();
  return str;
}
string char2str(char a) {
  stringstream ss;
  ss << a;
  string str = ss.str();
  return str;
}
long long int bigMod(long long int n, long long int power, long long int MOD) {
  if (power == 0) return 1;
  if (power % 2 == 0) {
    long long int ret = bigMod(n, power / 2, MOD);
    return ((ret % MOD) * (ret % MOD)) % MOD;
  } else
    return ((n % MOD) * (bigMod(n, power - 1, MOD) % MOD)) % MOD;
}
long long int modInverse(long long int a, long long int m) {
  long long int m0 = m, t, q;
  long long int x0 = 0, x1 = 1;
  if (m == 1) return 0;
  while (a > 1) {
    q = a / m;
    t = m;
    m = a % m, a = t;
    t = x0;
    x0 = x1 - q * x0;
    x1 = t;
  }
  if (x1 < 0) x1 += m0;
  return x1;
}
int POW(int x, int y) {
  int res = 1;
  for (; y;) {
    if ((y & 1)) {
      res *= x;
    }
    x *= x;
    y >>= 1;
  }
  return res;
}
int inverse(int x) {
  double p = ((double)1.0) / x;
  return (p) + 1e-9;
}
int gcd(int a, int b) {
  while (b) b ^= a ^= b ^= a %= b;
  return a;
}
int nC2(int n) { return n * (n - 1) / 2; }
long long int MOD(long long int n, long long int mod) {
  if (n >= 0)
    return n % mod;
  else if (-n == mod)
    return 0;
  else
    return mod + (n % mod);
}
long long int tree[1000005], temp[1000005];
int n, val[1000005];
vector<pair<int, int> > data;
void update(int i, long long int val) {
  while (i < 1000005) {
    tree[i] += val;
    i += i & (-i);
  }
}
long long int query(int i) {
  long long int sum = 0;
  while (i > 0) {
    sum += tree[i];
    i -= i & (-i);
  }
  return sum;
}
int main() {
  int t, cas = 0;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    int p;
    scanf("%d", &p);
    data.push_back(make_pair(p, i));
  }
  sort(data.begin(), data.end());
  int cnt = 0;
  for (int i = 0; i < data.size(); i++) {
    if (i > 0 && data[i].first == data[i - 1].first) {
      val[data[i].second] = cnt;
      continue;
    }
    val[data[i].second] = ++cnt;
  }
  for (int i = n; i >= 1; i--) {
    temp[i] = query(val[i] - 1);
    update(val[i], 1);
  }
  long long int ans = 0;
  memset(tree, 0, sizeof(tree));
  for (int i = n; i >= 1; i--) {
    ans += query(val[i] - 1);
    update(val[i], temp[i]);
  }
  printf("%lld\n", ans);
  return 0;
}

```