Ta cần chuẩn bị các mảng như sau:

• ~pre[i][j]~ là số ~a_i = j~ nằm trong đoạn từ ~[1..i]~
• ~suf[i][j]~ là số ~a_i = j~ nằm trong đoạn từ ~[i..n]~
• ~cnt[x][y]~ là số cặp ~(x, y)~ nằm trong prefix ~[1..i-1]~ đang xét

Xét bài toán tổng quát thì ta cần đếm số bộ ~4~ có dạng ~x..y..y..x~. Nếu ta cố định ~y~ thứ ~2~, thì tại vị trí ~i~ duyệt qua toàn bộ số ~x~ ~(1 \le x \le 100)~, đáp án sẽ được cộng thêm một khoảng là ~suf[i + 1][x] \times cnt[x][a_i]~. Sau đó ta cập nhật ~pre[i - 1][x]~ tương ứng cho ~cnt[x][a_i]~

Độ phức tạp: ~O(N \times 100)~

Code mẫu

/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")*/

#include <bits/stdc++.h>

#define for1(i,a,b) for (int i = a; i <= b; i++)
#define for2(i,a,b) for (int i = a; i >= b; i--)
#define int long long

#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pb push_back

/*
__builtin_popcountll(x) : Number of 1-bit
__builtin_ctzll(x) : Number of trailing 0
*/

const long double PI = 3.1415926535897932384626433832795;
const int INF = 1000000000000000000;
const int MOD = 1000000007;
const int MOD2 = 1000000009;
const long double EPS = 1e-6;

using namespace std;

const int N = 1e5 + 5, K = 105;
int n, res, cur1[K], cur2[K];
vector<int> v[K], sum[K];
int pre[N][K];

int get(int l, int r, int x) {
    return pre[r][x] - pre[l - 1][x];
}

signed main() {

    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    // freopen("cf.inp", "r", stdin);
    // freopen("cf.out", "w", stdout);

    cin >> n;
    for1(i,1,100) v[i] = {1};
    for1(i,1,n) {
        int a;
        cin >> a;
        v[a].push_back(i);
        for1(j,1,100) pre[i][j] = pre[i - 1][j];
        pre[i][a]++;
    }
    for1(i,1,100) v[i].push_back(n);

    for1(x,1,100) if (sz(v[x]) >= 4) {
        for1(i,1,100) sum[i] = {0};
        memset(cur1, 0, sizeof(cur1));
        memset(cur2, 0, sizeof(cur2));
        for1(p,1,sz(v[x]) - 2) {
            for1(i,1,100) {
                int val = sum[i].back() + get(v[x][p - 1], v[x][p] - 1, i);
                sum[i].push_back(val);
                cur1[i] += val;
            }
        }

        for2(p,sz(v[x]) - 2,2) {
            for1(i,1,100) {
                cur2[i] += get(v[x][p] + 1, v[x][p + 1], i);
                cur1[i] -= sum[i][p];
                // cout << x <<  " " << p << " " << i <<  " " << cur1[i] << " " << cur2[i] << "\n";
                res += cur1[i] * cur2[i];
            }
        }
        // cout << x << " " << res << "\n";
    }
    cout << res;
}