【題解】Codeforces 1400D. Zigzags

#include <iostream>
using namespace std;
 
int t, n, a[3005], bit[3005];
 
void update(int x){
    while (x <= n){
        bit[x]++;
        x += x & (-x);
    }
}
int query(int x){
    int ret = 0;
    while (x){
        ret += bit[x];
        x -= x & (-x);
    }
    return ret;
}
 
int main() {
    cin >> t;
    while (t--){
        cin >> n;
        for (int i = 1; i <= n; i++){
            cin >> a[i];
            bit[i] = 0;
        }
        long long ans = 0;
        for (int i = 1; i <= n; i++){
            for (int j = n; j >= i+2; j--){
                if (a[i] != a[j]) continue;
                ans += query(j-1)-query(i);
                update(j);
            }
        }
        cout << ans << "\n";
    }
}