#include "bits/stdc++.h" using namespace std; #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i)) #define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i)) static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL; typedef vector vi; typedef pair pii; typedef vector > vpii; typedef long long ll; template static void amin(T &x, U y) { if(y < x) x = y; } template static void amax(T &x, U y) { if(x < y) x = y; } #ifdef NDEBUG #error assert is disabled! #endif template T readNatural(T lo, T up) { assert(0 <= lo && lo <= up); T x = 0; while(1) { int d = getchar(); if(!('0' <= d && d <= '9')) { ungetc(d, stdin); break; } d -= '0'; assert(d <= up && x <= (up - d) / 10); x = x * 10 + d; } assert(lo <= x && x <= up); return x; } void readSpace() { int c = getchar(); assert(c == ' '); } static bool read_eof = false; void readEOL() { int c = getchar(); if(c == EOF) { assert(!read_eof); read_eof = true; } else { assert(c == '\n'); } } void readEOF() { assert(!read_eof); int c = getchar(); assert(c == EOF); read_eof = true; } struct FenwickTree { typedef int T; vector v; void init(int n) { v.assign(n, 0); } void add(int i, T x) { for(; i < (int)v.size(); i |= i + 1) v[i] += x; } T sum(int i) const { //[0, i) T r = 0; for(-- i; i >= 0; i = (i & (i + 1)) - 1) r += v[i]; return r; } T sum(int left, int right) const { //[left, right) return sum(right) - sum(left); } }; int main() { int N = readNatural(1, 100000); readEOL(); vector A(N); for(int i = 0; i < N; ++ i) { if(i != 0) readSpace(); A[i] = readNatural(1, (int)1e9); } readEOL(); readEOF(); vector values = A; sort(values.begin(), values.end()); values.erase(unique(values.begin(), values.end()), values.end()); for(vector::iterator it = A.begin(); it != A.end(); ++ it) *it = lower_bound(values.begin(), values.end(), *it) - values.begin(); int X = values.size(); vi cnt(X, 0), sum(X + 1, 0); rep(i, N) ++ cnt[A[i]]; rep(i, X) sum[i + 1] = sum[i] + cnt[i]; FenwickTree ft; ft.init(X); vi curcnt(X, 0); vector cursum(X, 0); vi firstpos(X, -1); ll ans = 0; rep(i, N) { int a = A[i]; int xL = ft.sum(a); int yL = i - xL - curcnt[a]; ans += (ll)xL * (sum[a] - xL); ans += (ll)yL * (sum[X] - sum[a + 1] - yL); ans -= (ll)curcnt[a] * (i - 1) - cursum[a]; ft.add(a, 1); ++ curcnt[a]; cursum[a] += i; } rep(a, X) { int n = cnt[a]; ans += (ll)n * (n - 1) * (n - 2) / 6; } printf("%lld\n", ans); return 0; }