这类找区间个数题，一般可以枚举一个端点，找符合条件的另一个端点的个数。
这题我们枚举右端点，对每个数x而言，其作为右端点的时候，满足条件的左端点必须是其前面2个x与前面3个x之间的点。
我们用lst[i][j],当前状态下，从后往前第j个i的位置。
显然：对于每个值i，都有：在区间[lst[i][3]+1 - lst[i][2]] 合法，其余点做为左端点均不合法。
由此有了做法：
从左往右枚举右端点，对于每个值，当前状态下，某个点可以作为左端点，则其值+1，否则不变。
显然，只有满足点值为0的点才是符合条件的左端点。
我们枚举右端点的同时不断改变每个点的值，始终保持对每个值，不在[lst[i][3]+1 - lst[i][2]] 的点的值均加1.
然后求出最小值是否为0，及最小值的个数，就是满足条件的左端点的个数。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define re register
#define ls (o<<1)
#define rs (o<<1|1)
#define pb push_back
const double PI= acos(-1.0);
const int M = 5e5+7;
ll tr[M<<2],nm[M<<2],tg[M<<2];
int lst[M][5],a[M];
void pu(int o)
{tr[ls]+=tg[o];tg[ls]+=tg[o];tr[rs]+=tg[o];tg[rs]+=tg[o];tg[o]=0;
}
void bd(int o,int l,int r)
{if(l==r){nm[o]=1;return ;}int m=(l+r)/2;bd(ls,l,m);bd(rs,m+1,r);
}
void up(int o,int l,int r,int x,int y,int d)//区间加法
{if(x<=l&&r<=y){tr[o]+=d;tg[o]+=d;return ;}pu(o);int m=(l+r)/2;if(x<=m)up(ls,l,m,x,y,d);if(y>m)up(rs,m+1,r,x,y,d); tr[o]=min(tr[ls],tr[rs]);if(tr[ls]<tr[rs])nm[o]=nm[ls];else if(tr[ls]>tr[rs])nm[o]=nm[rs];else nm[o]=nm[ls]+nm[rs];
}
struct node{ll x,nm;
};
const int inf = 1e7;
node qu(int o,int l,int r,int x,int y)//区间值为0的个数
{if(x<=l&&r<=y){return node{tr[o],nm[o]};}pu(o); int m=(l+r)/2;node tp={inf,0},a={inf,0},b={inf,0};if(x<=m)a=qu(ls,l,m,x,y);if(y>m)b=qu(rs,m+1,r,x,y); tp.x=min(a.x,b.x);if(a.x<b.x)tp.nm=a.nm;else if(a.x>b.x)tp.nm=b.nm;else tp.nm=a.nm+b.nm;return tp;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);int n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];ll ans=0;bd(1,1,n);for(int i=1;i<=n;i++){up(1,1,n,lst[a[i]][1]+1,i,1);if(lst[a[i]][3]+1<=lst[a[i]][2])up(1,1,n,lst[a[i]][3]+1,lst[a[i]][2],-1);if(lst[a[i]][4]+1<=lst[a[i]][3])up(1,1,n,lst[a[i]][4]+1,lst[a[i]][3],1);node tp=qu(1,1,n,1,i);
// cout<<i<<" - - ";
// for(int j=1;j<=n;j++)
// {
// node t=qu(1,1,n,j,j);
// cout<<t.x<<" ";
// }
// cout<<endl;
// cout<<i<<" ："<<tp.x<< " "<<tp.nm<<endl;if(tp.x==0)ans+=tp.nm ;lst[a[i]][4]=lst[a[i]][3];lst[a[i]][3]=lst[a[i]][2];lst[a[i]][2]=lst[a[i]][1];lst[a[i]][1]=i; }cout<<ans<<endl;return 0;
}