#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define endl '\n' #define ALL(v) (v).begin(), (v).end() #define RALL(v) (v).rbegin(), (v).rend() #define UNIQ(v) (v).erase(unique((v).begin(), (v).end()), (v).end()) typedef long long ll; typedef long double ld; typedef pair P; typedef complex comp; typedef vector< vector > matrix; struct pairhash { public: template size_t operator()(const pair &x) const { size_t seed = hash()(x.first); return hash()(x.second) + 0x9e3779b9 + (seed<<6) + (seed>>2); } }; const int inf = 1e9 + 9; const ll mod = 1e9 + 7; const double eps = 1e-8; const double pi = acos(-1); int N; int a[1000100]; // 1 base template class BIT { private: T bit[max_n + 1]; int n; public: BIT(int _n = max_n) { n = _n; memset(bit, 0, sizeof(bit)); } // [1, i] T sum(int i) { T s = 0; while (i > 0) { s += bit[i]; i -= i & -i; } return s; } // [a, b] T sum(int a, int b) { return sum(b) - sum(a-1); } void add(int i, T x) { while (i <= n) { bit[i] += x; i += i & -i; } } int lower_bound(T x) { int lb = 0, ub = n; while (ub - lb > 1) { int mid = (ub + lb) / 2; T v = sum(mid); if (v < x) { lb = mid; } else { ub = mid; } } return ub; } int upper_bound(T x) { int lb = 1, ub = n+1; while (ub - lb > 1) { int mid = (ub + lb) / 2; T v = sum(mid); if (v <= x) { lb = mid; } else { ub = mid; } } return ub; } }; int c[1000100]; BIT rbit; BIT fbit; ll solve() { vector aa; for (int i = 0; i < N; i++) aa.push_back(a[i]); sort(ALL(aa)); UNIQ(aa); int l = aa.size(); for (int i = 0; i < l; i++) { c[aa[i]] = i+1; } ll same = 0, res = 0; for (int i = 2; i < N; i++) { rbit.add(c[a[i]], 1); } fbit.add(c[a[0]], 1); same = rbit.sum(c[a[0]], c[a[0]]); for (int i = 1; i < N-1; i++) { res += fbit.sum(c[a[i]]-1) * rbit.sum(c[a[i]]-1) + fbit.sum(c[a[i]]+1, l) * rbit.sum(c[a[i]]+1, l) - same + fbit.sum(c[a[i]], c[a[i]]) * rbit.sum(c[a[i]], c[a[i]]); fbit.add(c[a[i]], 1); same += rbit.sum(c[a[i]], c[a[i]]); rbit.add(c[a[i+1]], -1); same -= fbit.sum(c[a[i+1]], c[a[i+1]]); } return res; } void input() { cin >> N; for (int i = 0; i < N; i++) cin >> a[i]; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(15); input(); cout << solve() << endl; }