#include <bits/stdc++.h>
using namespace std;
template <class T>
void UniqeVector(vector<T>& v) {
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), end(v));
}
template <class A>
void re(complex<A>& c);
template <class A, class B>
void re(pair<A, B>& p);
template <class A>
void re(vector<A>& v);
template <class A, size_t SZ>
void re(array<A, SZ>& a);
template <class T>
void re(T& x) {
  cin >> x;
}
void re(double& d) {
  string t;
  re(t);
  d = stod(t);
}
void re(long double& d) {
  string t;
  re(t);
  d = stold(t);
}
template <class H, class... T>
void re(H& h, T&... t) {
  re(h);
  re(t...);
}
template <class A>
void re(complex<A>& c) {
  A a, b;
  re(a, b);
  c = {a, b};
}
template <class A, class B>
void re(pair<A, B>& p) {
  re(p.f, p.s);
}
template <class A>
void re(vector<A>& x) {
  for (auto& a : x) re(a);
}
template <class A, size_t SZ>
void re(array<A, SZ>& x) {
  for (auto& a : x) re(a);
}
string to_string(char c) { return string(1, c); }
string to_string(const char* s) { return (string)s; }
string to_string(string s) { return s; }
string to_string(bool b) { return to_string((int)b); }
template <class A>
string to_string(complex<A> c) {
  stringstream ss;
  ss << c;
  return ss.str();
}
string to_string(vector<bool> v) {
  string res = "{";
  for (int i = (0); ((1) > 0 ? i < ((int)v.size()) : i > ((int)v.size()));
       i += (1))
    res += char('0' + v[i]);
  res += "}";
  return res;
}
template <size_t SZ>
string to_string(bitset<SZ> b) {
  string res = "";
  for (int i = (0); ((1) > 0 ? i < (SZ) : i > (SZ)); i += (1))
    res += char('0' + b[i]);
  return res;
}
template <class A, class B>
string to_string(pair<A, B> p);
template <class T>
string to_string(T v) {
  bool fst = 1;
  string res = "";
  for (const auto& x : v) {
    if (!fst) res += " ";
    fst = 0;
    res += to_string(x);
  }
  return res;
}
template <class A, class B>
string to_string(pair<A, B> p) {
  return to_string(p.f) + " " + to_string(p.s);
}
template <class A>
void pr(A x) {
  cout << to_string(x);
}
template <class H, class... T>
void pr(const H& h, const T&... t) {
  pr(h);
  pr(t...);
}
void ps() { pr("\n"); }
template <class H, class... T>
void ps(const H& h, const T&... t) {
  pr(h);
  if (sizeof...(t)) pr(" ");
  ps(t...);
}
void prsz(vector<int>& v) {
  pr((int)v.size(), '\n');
  pr(v);
}
const int di[8] = {0, 0, 1, -1, 1, 1, -1, -1};
const int dj[8] = {1, -1, 0, 0, 1, -1, 1, -1};
struct Fenwick {
  vector<long long> bit;
  int sz;
  void init(int n) {
    sz = (1 << (int)ceil(log2(n + 1)));
    bit.resize(sz + 1);
  }
  long long query(int x) {
    long long sum = 0;
    for (; x; x -= x & -x) {
      sum += bit[x];
    }
    return sum;
  }
  void update(int x, long long val) {
    for (; x <= sz; x += x & -x) bit[x] += val;
  }
  long long Sum(int st, int en) { return query(en) - query(st - 1); }
  void Clear() {
    for (int i = 0; i <= sz; ++i) bit[i] = 0;
  }
  int FindIdx(long long v) {
    int l = 1, r = sz;
    while (l < r) {
      int mid = l + (r - l) / 2;
      if (bit[mid] < v)
        l = mid + 1, v -= bit[mid];
      else
        r = mid;
    }
    return l;
  }
};
void Suhaib_Sawalha() {
  int n;
  re(n);
  vector<int> v(n);
  set<int> co;
  for (auto& x : v) {
    re(x);
    co.insert(x);
  }
  map<int, int> comp;
  n = 0;
  for (auto& x : co) comp[x] = ++n;
  Fenwick fen;
  Fenwick fen2;
  fen.init(n);
  fen2.init(n);
  long long ans = 0;
  for (int i = (int)v.size() - 1; ~i; --i) {
    ans += fen.query(comp[v[i]] - 1);
    fen.update(comp[v[i]], fen2.query(comp[v[i]] - 1));
    fen2.update(comp[v[i]], 1);
  }
  cout << ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  Suhaib_Sawalha();
  return 0;
}

### 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;
template <class T>
void UniqeVector(vector<T>& v) {
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), end(v));
}
template <class A>
void re(complex<A>& c);
template <class A, class B>
void re(pair<A, B>& p);
template <class A>
void re(vector<A>& v);
template <class A, size_t SZ>
void re(array<A, SZ>& a);
template <class T>
void re(T& x) {
  cin >> x;
}
void re(double& d) {
  string t;
  re(t);
  d = stod(t);
}
void re(long double& d) {
  string t;
  re(t);
  d = stold(t);
}
template <class H, class... T>
void re(H& h, T&... t) {
  re(h);
  re(t...);
}
template <class A>
void re(complex<A>& c) {
  A a, b;
  re(a, b);
  c = {a, b};
}
template <class A, class B>
void re(pair<A, B>& p) {
  re(p.f, p.s);
}
template <class A>
void re(vector<A>& x) {
  for (auto& a : x) re(a);
}
template <class A, size_t SZ>
void re(array<A, SZ>& x) {
  for (auto& a : x) re(a);
}
string to_string(char c) { return string(1, c); }
string to_string(const char* s) { return (string)s; }
string to_string(string s) { return s; }
string to_string(bool b) { return to_string((int)b); }
template <class A>
string to_string(complex<A> c) {
  stringstream ss;
  ss << c;
  return ss.str();
}
string to_string(vector<bool> v) {
  string res = "{";
  for (int i = (0); ((1) > 0 ? i < ((int)v.size()) : i > ((int)v.size()));
       i += (1))
    res += char('0' + v[i]);
  res += "}";
  return res;
}
template <size_t SZ>
string to_string(bitset<SZ> b) {
  string res = "";
  for (int i = (0); ((1) > 0 ? i < (SZ) : i > (SZ)); i += (1))
    res += char('0' + b[i]);
  return res;
}
template <class A, class B>
string to_string(pair<A, B> p);
template <class T>
string to_string(T v) {
  bool fst = 1;
  string res = "";
  for (const auto& x : v) {
    if (!fst) res += " ";
    fst = 0;
    res += to_string(x);
  }
  return res;
}
template <class A, class B>
string to_string(pair<A, B> p) {
  return to_string(p.f) + " " + to_string(p.s);
}
template <class A>
void pr(A x) {
  cout << to_string(x);
}
template <class H, class... T>
void pr(const H& h, const T&... t) {
  pr(h);
  pr(t...);
}
void ps() { pr("\n"); }
template <class H, class... T>
void ps(const H& h, const T&... t) {
  pr(h);
  if (sizeof...(t)) pr(" ");
  ps(t...);
}
void prsz(vector<int>& v) {
  pr((int)v.size(), '\n');
  pr(v);
}
const int di[8] = {0, 0, 1, -1, 1, 1, -1, -1};
const int dj[8] = {1, -1, 0, 0, 1, -1, 1, -1};
struct Fenwick {
  vector<long long> bit;
  int sz;
  void init(int n) {
    sz = (1 << (int)ceil(log2(n + 1)));
    bit.resize(sz + 1);
  }
  long long query(int x) {
    long long sum = 0;
    for (; x; x -= x & -x) {
      sum += bit[x];
    }
    return sum;
  }
  void update(int x, long long val) {
    for (; x <= sz; x += x & -x) bit[x] += val;
  }
  long long Sum(int st, int en) { return query(en) - query(st - 1); }
  void Clear() {
    for (int i = 0; i <= sz; ++i) bit[i] = 0;
  }
  int FindIdx(long long v) {
    int l = 1, r = sz;
    while (l < r) {
      int mid = l + (r - l) / 2;
      if (bit[mid] < v)
        l = mid + 1, v -= bit[mid];
      else
        r = mid;
    }
    return l;
  }
};
void Suhaib_Sawalha() {
  int n;
  re(n);
  vector<int> v(n);
  set<int> co;
  for (auto& x : v) {
    re(x);
    co.insert(x);
  }
  map<int, int> comp;
  n = 0;
  for (auto& x : co) comp[x] = ++n;
  Fenwick fen;
  Fenwick fen2;
  fen.init(n);
  fen2.init(n);
  long long ans = 0;
  for (int i = (int)v.size() - 1; ~i; --i) {
    ans += fen.query(comp[v[i]] - 1);
    fen.update(comp[v[i]], fen2.query(comp[v[i]] - 1));
    fen2.update(comp[v[i]], 1);
  }
  cout << ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  Suhaib_Sawalha();
  return 0;
}

```