uusF93 - Online C++ Compiler & Debugging Tool

#include <iostream>
#include <vector>
#include <algorithm>
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];

    ll tot = 1LL*n*(n+1)/2;
    ll bad = 0;

    for(int v=1; v<=500000; v++){
        int cur = 0;
        vector<int> pre;
        pre.reserve(n+1);
        pre.push_back(0);

        for(int i=0;i<n;i++){
            cur += (a[i]==v ? 1 : -1);
            pre.push_back(cur);
        }

        vector<int> s = pre;
        sort(s.begin(), s.end());

        for(int i=0;i<(int)pre.size();i++){
            int x = pre[i];
            bad += lower_bound(s.begin(), s.end(), x) - s.begin();
        }
    }

    cout << tot - bad;
}