算法

(树状数组) $O(n\log n)$

考虑枚举中间的 $j$， 这样只需要计算出有多少个对应的 $i$，$k$。
如果一个 $j$ 有$left[j]$ 个对应的 $i$ 和 $right[j]$ 个对应的 $k$，那么它会贡献 $left[j] * right[j]$ 的答案。
考虑计算 $left[j]$
直接树状数组即可。
$right[j]$ 的计算同理，倒过来即可。

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
using ll = long long;

const int N = 3e4 + 10;

ll n;
ll a[N], cnt[N], cntl[N], cntr[N];

void add(ll x) {
    while (x <= n) {
        cnt[x]++;
        x += x & -x;
    }
}

ll sum(ll x) {
    ll s = 0;
    while (x > 0) {
        s += cnt[x];
        x -= x & -x;
    }
    return s;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];

    vector<int> v;
    for (int i = 1; i <= n; ++i) 
         v.push_back(a[i]);
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    for (int i = 1; i <= n; ++i) {
        a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;
    }

    for (int i = 1; i <= n; ++i) {
        cntl[i] = sum(a[i] - 1);
        add(a[i]);
    }

    fill(cnt + 1, cnt + n + 1, 0);

    for (int i = n; i >= 1; --i) {
        cntr[i] = sum(n - a[i]);
        add(n - a[i] + 1);
    }

    ll ans = 0;
    for (int i = 1; i <= n; ++i) 
         ans += cntl[i] * cntr[i];

    cout << ans << '\n';

    return 0;
}