性感猫娘在线求调~

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define ull unsigned long long
#define rd read()
#define mkp make_pair
#define psb push_back
#define Elaina 0
#define mst(a,b) memset((a),(b),sizeof(a))
#define random(a,b) (1ll*rand()*rand()*rand()%((b)-(a)+1)+(a))
inline ll read(){
	ll f=1,x=0;
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar()) f=(ch=='-'?-1:1);
	for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';
	return f*x;
}
const int mod=1e9+7;
const int N=1e6+100;
const int inf=0x7fffffff;

int n,k;

int max(int a,int b){
	return a>b?a:b;
}

mt19937_64 rnd(time(0));

ull code[N],pre[N],a[N],bkt[N];
map<ull,ull> mp; 

ull xork(ull x,ull y,int k){
	ull sum=0,p=1;
	while(x||y){
		sum+=(x%k+y%k)%k*p;
		p*=k;
		x/=k;
		y/=k;
	}
	return sum;
}


signed main(){
	srand(time(0));
	
	n=rd,k=3;
	for(int i=1;i<=n;i++){
		a[i]=rd;
	}
	
	for(int i=1;i<=N;i++){
		code[i]=rnd();
	}
	
	for(int i=1;i<=n;i++){
		pre[i]=xork(pre[i-1],code[a[i]],k);
//		cout<<pre[i]<<endl;
	}
	
	int cnt=0;
	mp[0]=1;
	for(int l=0,r=1;r<=n;++r){
		++bkt[a[r]];
		while(bkt[a[r]]>3){
			--bkt[a[l]];
			if(l>0) --mp[pre[l-1]];
			++l;
		}
		cnt+=mp[pre[r]];
//		cout<<cnt<<endl;
		++mp[pre[r]];
	}
	
	printf("%lld",cnt);
	return Elaina;
}