MYDdqr - Online C++ Compiler & Debugging Tool

#include <iostream>
#include <vector>
using namespace std;

using ll = long long;

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

    int n;
    cin >> n;

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

    const int MAXA = 500000;
    vector<vector<int>> pos(MAXA + 1);

    for (int i = 0; i < n; i++)
        pos[a[i]].push_back(i);

    ll bad = 0;

    for (int v = 1; v <= MAXA; v++) {
        auto &p = pos[v];
        int m = p.size();
        if (m <= 1) continue;

        int j = 0;
        for (int i = 0; i < m; i++) {
            if (j < i) j = i;
            while (j + 1 < m && p[j + 1] - p[i] + 1 < 2 * (j - i + 2))
                j++;
            bad += (j - i);
        }
    }

    ll total = 1LL * n * (n + 1) / 2;
    cout << total - bad;
}