e.cpp

#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
using namespace std;
int n, m, q;
const int MAXN = 1e6 + 10;
const int INF = 1e9 + 7;
int a[MAXN], b[MAXN];
vector <int> t_pref(MAXN * 4, 0);
vector <int> t_suf(MAXN * 4, 0);

void update(vector <int> &t, int v, int tl, int tr, int pos, int val){
    if (tl > tr){
        return;
    }
    if (tl == tr){
        t[v] += val;
        return;
    }
    int tm = (tl + tr) / 2;
    if (pos <= tm){
        update(t, v + v, tl, tm, pos, val);
    }
    else{
        update(t, v + v + 1, tm + 1, tr, pos, val);
    }
    t[v] = t[v + v] + t[v + v + 1];
}

int get_sum(vector <int> &t, int v, int tl, int tr, int l, int r){
    if (l > r){
        return 0;
    }
    if (tl == l && tr == r){
        return t[v];
    }
    int tm = (tl + tr) / 2;
    return get_sum(t, v + v, tl , tm, l, min(r, tm)) +
        get_sum(t, v + v + 1, tm + 1, tr, max(l, tm + 1), r);
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        b[i] = a[i];
    }
    sort(b + 1, b + n + 1);
    int timer = 1;
    map <int, int> ma;
    ma[b[1]] = timer;
    for (int i = 2; i <= n; i++){
        if (b[i] != b[i - 1]){
            timer++;
            ma[b[i]] = timer;
        }
    }

    for (int i = 1; i <= n; i++){
        a[i] = ma[a[i]];
        update(t_suf, 1, 1, n, a[i], 1);
    }
    ll ans = 0;
    for (int j = 1; j <= n; j++){
        update(t_suf, 1, 1, n, a[j], -1);
        int val1 = get_sum(t_pref, 1, 1, n, a[j] + 1, n);
        int val2 = get_sum(t_suf, 1, 1, n, 1, a[j] - 1);
        ans += 1LL * val1 * val2;
        update(t_pref, 1, 1, n, a[j], 1);
    }
    cout << ans;
}