#include <bits/stdc++.h>
using namespace std;
long long int mod = 1000000007;
int make_segment(long long int arr[], int index, int l, int r, int ar[]) {
  if (l == r) {
    arr[index] = ar[l];
    return ar[l];
  }
  int mid = (l + r) / 2;
  int sum = 0;
  sum += make_segment(arr, 2 * index + 1, l, mid, ar);
  sum += make_segment(arr, 2 * index + 2, mid + 1, r, ar);
  arr[index] = sum;
  return sum;
}
void add1(long long int arr[], int index, int d) {
  if (index == 0) {
    arr[index] += (long long int)d;
    return;
  }
  arr[index] += (long long int)d;
  add1(arr, (index - 1) / 2, d);
}
long long int find_sum(long long int arr[], int index, int l, int r, int L,
                       int R) {
  if (l > R || L > r) return 0;
  if (L <= l && r <= R) return arr[index];
  int mid = (l + r) / 2;
  long long int sum = 0;
  sum += find_sum(arr, 2 * index + 1, l, mid, L, R);
  sum += find_sum(arr, 2 * index + 2, mid + 1, r, L, R);
  return sum;
}
long long int arr[2097151];
int ar[1000001], Cr[1000001];
int main() {
  int x, y = 1;
  cin >> x;
  map<int, int> mp;
  for (int i = 0; i < x; i++) {
    cin >> ar[i];
  }
  for (int i = x - 1; i >= 0; i--) {
    mp[ar[i]] = i;
  }
  map<int, int>::iterator itr;
  for (itr = mp.begin(); itr != mp.end(); ++itr) {
    ar[itr->second] = y;
    y++;
  }
  y = 2 * pow(2, (int)ceil((1.0 * log(x)) / log(2))) - 1;
  int l, r, mid, c, index, k;
  long long int sum = 0;
  for (int i = x - 1; i >= 0; i--) {
    c = ar[i] - 1;
    l = 0;
    r = x - 1;
    index = 0;
    while (1) {
      if (l == r && l == c) break;
      mid = (l + r) / 2;
      if (mid >= c) {
        r = mid;
        index = 2 * index + 1;
      } else {
        l = mid + 1;
        index = 2 * index + 2;
      }
    }
    add1(arr, index, 1);
    if (c == 0) {
      Cr[i] = 0;
      continue;
    }
    Cr[i] = find_sum(arr, 0, 0, x - 1, 0, c - 1);
  }
  for (int i = 0; i < y; i++) arr[i] = 0;
  for (int i = x - 1; i >= 0; i--) {
    c = ar[i] - 1;
    l = 0;
    r = x - 1;
    index = 0;
    while (1) {
      if (l == r && l == c) break;
      mid = (l + r) / 2;
      if (mid >= c) {
        r = mid;
        index = 2 * index + 1;
      } else {
        l = mid + 1;
        index = 2 * index + 2;
      }
    }
    add1(arr, index, Cr[i]);
    if (c == 0) {
      continue;
    }
    sum += find_sum(arr, 0, 0, x - 1, 0, c - 1);
  }
  cout << sum;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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;
long long int mod = 1000000007;
int make_segment(long long int arr[], int index, int l, int r, int ar[]) {
  if (l == r) {
    arr[index] = ar[l];
    return ar[l];
  }
  int mid = (l + r) / 2;
  int sum = 0;
  sum += make_segment(arr, 2 * index + 1, l, mid, ar);
  sum += make_segment(arr, 2 * index + 2, mid + 1, r, ar);
  arr[index] = sum;
  return sum;
}
void add1(long long int arr[], int index, int d) {
  if (index == 0) {
    arr[index] += (long long int)d;
    return;
  }
  arr[index] += (long long int)d;
  add1(arr, (index - 1) / 2, d);
}
long long int find_sum(long long int arr[], int index, int l, int r, int L,
                       int R) {
  if (l > R || L > r) return 0;
  if (L <= l && r <= R) return arr[index];
  int mid = (l + r) / 2;
  long long int sum = 0;
  sum += find_sum(arr, 2 * index + 1, l, mid, L, R);
  sum += find_sum(arr, 2 * index + 2, mid + 1, r, L, R);
  return sum;
}
long long int arr[2097151];
int ar[1000001], Cr[1000001];
int main() {
  int x, y = 1;
  cin >> x;
  map<int, int> mp;
  for (int i = 0; i < x; i++) {
    cin >> ar[i];
  }
  for (int i = x - 1; i >= 0; i--) {
    mp[ar[i]] = i;
  }
  map<int, int>::iterator itr;
  for (itr = mp.begin(); itr != mp.end(); ++itr) {
    ar[itr->second] = y;
    y++;
  }
  y = 2 * pow(2, (int)ceil((1.0 * log(x)) / log(2))) - 1;
  int l, r, mid, c, index, k;
  long long int sum = 0;
  for (int i = x - 1; i >= 0; i--) {
    c = ar[i] - 1;
    l = 0;
    r = x - 1;
    index = 0;
    while (1) {
      if (l == r && l == c) break;
      mid = (l + r) / 2;
      if (mid >= c) {
        r = mid;
        index = 2 * index + 1;
      } else {
        l = mid + 1;
        index = 2 * index + 2;
      }
    }
    add1(arr, index, 1);
    if (c == 0) {
      Cr[i] = 0;
      continue;
    }
    Cr[i] = find_sum(arr, 0, 0, x - 1, 0, c - 1);
  }
  for (int i = 0; i < y; i++) arr[i] = 0;
  for (int i = x - 1; i >= 0; i--) {
    c = ar[i] - 1;
    l = 0;
    r = x - 1;
    index = 0;
    while (1) {
      if (l == r && l == c) break;
      mid = (l + r) / 2;
      if (mid >= c) {
        r = mid;
        index = 2 * index + 1;
      } else {
        l = mid + 1;
        index = 2 * index + 2;
      }
    }
    add1(arr, index, Cr[i]);
    if (c == 0) {
      continue;
    }
    sum += find_sum(arr, 0, 0, x - 1, 0, c - 1);
  }
  cout << sum;
}

```