#include <bits/stdc++.h>
using namespace std;
int a[1000001];
pair<int, int> b[1000001];
int st[2097200];
int leftmost[2097200];
int rightmost[2097200];
long long min_max[2][1000001];
int n2;
int sigPot2(int n) {
  int p = 1;
  while (p < n) p *= 2;
  return p;
}
int pos;
void update(int n) {
  if (n >= n2) {
    if (n == pos) st[n]++;
    return;
  }
  if (leftmost[n] <= pos && pos <= rightmost[n]) {
    st[n]++;
    update(n << 1);
    update((n << 1) | 1);
  }
}
int maximo;
int query(int n) {
  if (n >= n2) {
    if (n == maximo) return st[n];
    return 0;
  }
  if (rightmost[n] <= maximo) return st[n];
  if (leftmost[n] <= maximo) return query(n << 1) + query((n << 1) | 1);
  return 0;
}
void calcular(int m, int n) {
  for (int i = 0; i < n; i++) {
    maximo = n2 + a[i] - 1;
    int q = query(1);
    if (m == 0)
      min_max[m][i] = q;
    else
      min_max[m][n - 1 - i] = q;
    pos = n2 + a[i] - 1;
    update(1);
  }
}
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
    b[i].first = a[i];
    b[i].second = i;
  }
  sort(b, b + n);
  for (int i = 0; i < n; i++) a[b[i].second] = n - i;
  n2 = sigPot2(n);
  for (int i = n2; i < n2 * 2; i++) leftmost[i] = rightmost[i] = i;
  for (int i = n2 - 1; i >= 1; i--) {
    leftmost[i] = leftmost[i << 1];
    rightmost[i] = rightmost[(i << 1) | 1];
  }
  calcular(0, n);
  reverse(a, a + n);
  for (int i = 0; i < n; i++) a[i] = n + 1 - a[i];
  memset(st, 0, sizeof(int) * 2097200);
  calcular(1, n);
  long long res = 0;
  for (int i = 0; i < n; i++) res += min_max[0][i] * min_max[1][i];
  printf("%I64d\n", res);
  return 0;
}

### Prompt

Your task is to create a CPP solution 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 a[1000001];
pair<int, int> b[1000001];
int st[2097200];
int leftmost[2097200];
int rightmost[2097200];
long long min_max[2][1000001];
int n2;
int sigPot2(int n) {
  int p = 1;
  while (p < n) p *= 2;
  return p;
}
int pos;
void update(int n) {
  if (n >= n2) {
    if (n == pos) st[n]++;
    return;
  }
  if (leftmost[n] <= pos && pos <= rightmost[n]) {
    st[n]++;
    update(n << 1);
    update((n << 1) | 1);
  }
}
int maximo;
int query(int n) {
  if (n >= n2) {
    if (n == maximo) return st[n];
    return 0;
  }
  if (rightmost[n] <= maximo) return st[n];
  if (leftmost[n] <= maximo) return query(n << 1) + query((n << 1) | 1);
  return 0;
}
void calcular(int m, int n) {
  for (int i = 0; i < n; i++) {
    maximo = n2 + a[i] - 1;
    int q = query(1);
    if (m == 0)
      min_max[m][i] = q;
    else
      min_max[m][n - 1 - i] = q;
    pos = n2 + a[i] - 1;
    update(1);
  }
}
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
    b[i].first = a[i];
    b[i].second = i;
  }
  sort(b, b + n);
  for (int i = 0; i < n; i++) a[b[i].second] = n - i;
  n2 = sigPot2(n);
  for (int i = n2; i < n2 * 2; i++) leftmost[i] = rightmost[i] = i;
  for (int i = n2 - 1; i >= 1; i--) {
    leftmost[i] = leftmost[i << 1];
    rightmost[i] = rightmost[(i << 1) | 1];
  }
  calcular(0, n);
  reverse(a, a + n);
  for (int i = 0; i < n; i++) a[i] = n + 1 - a[i];
  memset(st, 0, sizeof(int) * 2097200);
  calcular(1, n);
  long long res = 0;
  for (int i = 0; i < n; i++) res += min_max[0][i] * min_max[1][i];
  printf("%I64d\n", res);
  return 0;
}

```