求调CF1418G

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mpr make_pair
#define ld double
#define sdn cout
#define vi vector<int>
#define ull unsigned long long
#define fi first
#define se second
#define pii pair<int,int>
mt19937 rnd(time(0));

const int N = 5e5 + 10,M = 1e6 + 10,INF1 = 1e9 + 7;
const ll INF2 = 1e18 + 7,MOD = 998244353;
const ull base = 131;

ll n,m,k,q,T,rt,a[N],cnt[N];
ll ans,rd[N];
__int128 h[N];
map<__int128,ll> mp;
int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n;
    for(int i = 1;i <= n;i ++)  rd[i] = rnd()%INF2+1;
    for(int i = 1;i <= n;i ++){
        cin>>a[i];h[i] = h[i-1];
        h[i] -= cnt[a[i]]*rd[a[i]];
        cnt[a[i]] = (cnt[a[i]]+1)%3;
        h[i] += cnt[a[i]]*rd[a[i]];
    }
    int l = 0;
    mp[0] = 1;
    for(int i = 0;i <= n;i ++)  cnt[i] = 0;
    for(int r = 1;r <= n;r ++){
        cnt[a[r]] ++;
        while(cnt[a[r]] > 3){
            cnt[a[l]] --;
            if(l)  mp[h[l-1]] --;
            l ++;
        }
        ans += mp[h[r]];
        mp[h[r]] ++; 
    }
    sdn<<ans<<endl;
    return 0;
}