#include <bits/stdc++.h>
const long long maxn = 1e6 + 10;
long long seg[maxn << 2][2];
long long N, arr[maxn];
std::vector<long long> v;
inline long long getid(long long x) {
  return std::lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}
void update(long long l, long long r, long long pos, long long cur,
            long long val, long long tree) {
  if (l == r) {
    seg[cur][tree] = val;
    return;
  }
  long long mid = (l + r) >> 1;
  if (mid >= pos) {
    update(l, mid, pos, cur << 1, val, tree);
  } else {
    update(mid + 1, r, pos, cur << 1 | 1, val, tree);
  }
  seg[cur][tree] = seg[cur << 1][tree] + seg[cur << 1 | 1][tree];
}
long long query(long long l, long long r, long long L, long long R,
                long long cur, long long tree) {
  if (L > R) return 0;
  if (l >= L && r <= R) {
    return seg[cur][tree];
  }
  long long mid = (l + r) >> 1, ans = 0;
  if (mid >= L) ans += query(l, mid, L, R, cur << 1, tree);
  if (mid < R) ans += query(mid + 1, r, L, R, cur << 1 | 1, tree);
  return ans;
}
inline long long read() {
  long long f = 1, r = 0;
  char c = getchar();
  while (!isdigit(c)) {
    if (c == '-') {
      f = -1;
    }
    c = getchar();
  }
  while (isdigit(c)) {
    r = 10 * r + c - '0';
    c = getchar();
  }
  return f * r;
}
inline void write(long long x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}
inline void writesp(long long x) { write(x), putchar(' '); }
inline void writeln(long long x) { write(x), puts(""); }
signed main() {
  N = read();
  for (register long long i = 1; i <= N; ++i) {
    arr[i] = read();
    v.push_back(arr[i]);
  }
  std::sort(v.begin(), v.end());
  v.erase(std::unique(v.begin(), v.end()), v.end());
  for (long long i = 1; i <= N; ++i) {
    long long id = getid(arr[i]);
    update(1, v.size(), id, 1, 1, 1);
  }
  long long ans = 0;
  for (long long i = 1; i <= N; ++i) {
    long long id = getid(arr[i]);
    long long bigger = query(1, v.size(), id + 1, v.size(), 1, 0);
    long long smaller = query(1, v.size(), 1, id - 1, 1, 1);
    ans += smaller * bigger;
    update(1, v.size(), id, 1, 0, 1);
    update(1, v.size(), id, 1, 1, 0);
  }
  writeln(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>
const long long maxn = 1e6 + 10;
long long seg[maxn << 2][2];
long long N, arr[maxn];
std::vector<long long> v;
inline long long getid(long long x) {
  return std::lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}
void update(long long l, long long r, long long pos, long long cur,
            long long val, long long tree) {
  if (l == r) {
    seg[cur][tree] = val;
    return;
  }
  long long mid = (l + r) >> 1;
  if (mid >= pos) {
    update(l, mid, pos, cur << 1, val, tree);
  } else {
    update(mid + 1, r, pos, cur << 1 | 1, val, tree);
  }
  seg[cur][tree] = seg[cur << 1][tree] + seg[cur << 1 | 1][tree];
}
long long query(long long l, long long r, long long L, long long R,
                long long cur, long long tree) {
  if (L > R) return 0;
  if (l >= L && r <= R) {
    return seg[cur][tree];
  }
  long long mid = (l + r) >> 1, ans = 0;
  if (mid >= L) ans += query(l, mid, L, R, cur << 1, tree);
  if (mid < R) ans += query(mid + 1, r, L, R, cur << 1 | 1, tree);
  return ans;
}
inline long long read() {
  long long f = 1, r = 0;
  char c = getchar();
  while (!isdigit(c)) {
    if (c == '-') {
      f = -1;
    }
    c = getchar();
  }
  while (isdigit(c)) {
    r = 10 * r + c - '0';
    c = getchar();
  }
  return f * r;
}
inline void write(long long x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}
inline void writesp(long long x) { write(x), putchar(' '); }
inline void writeln(long long x) { write(x), puts(""); }
signed main() {
  N = read();
  for (register long long i = 1; i <= N; ++i) {
    arr[i] = read();
    v.push_back(arr[i]);
  }
  std::sort(v.begin(), v.end());
  v.erase(std::unique(v.begin(), v.end()), v.end());
  for (long long i = 1; i <= N; ++i) {
    long long id = getid(arr[i]);
    update(1, v.size(), id, 1, 1, 1);
  }
  long long ans = 0;
  for (long long i = 1; i <= N; ++i) {
    long long id = getid(arr[i]);
    long long bigger = query(1, v.size(), id + 1, v.size(), 1, 0);
    long long smaller = query(1, v.size(), 1, id - 1, 1, 1);
    ans += smaller * bigger;
    update(1, v.size(), id, 1, 0, 1);
    update(1, v.size(), id, 1, 1, 0);
  }
  writeln(ans);
  return 0;
}

```