我写了个$n^2$的暴力就过了，是我分析错复杂度了，还是题目数据水啊/yun

//μ's forever
#include <bits/stdc++.h>
#define N 300005
#define ll long long
//#define getchar nc
using namespace std;
inline char nc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
    register int x=0,f=1;register char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return x*f;
}
inline void write(register ll x)
{
    if(!x)putchar('0');if(x<0)x=-x,putchar('-');
    static int sta[20];register int tot=0;
    while(x)sta[tot++]=x%10,x/=10;
    while(tot)putchar(sta[--tot]+48);
}
int T,n,a[N],pre[N],nxt[N],f[N];
vector<int> v[N];
int mn[N<<2],mx[N<<2];
inline void build(register int x,register int l,register int r){
    if(l==r){ mn[x]=pre[l],mx[x]=nxt[l]; return; }
    int mid=l+r>>1;
    build(x<<1,l,mid),build(x<<1|1,mid+1,r);
    mn[x]=min(mn[x<<1],mn[x<<1|1]),mx[x]=max(mx[x<<1],mx[x<<1|1]);
}
inline pair<int,int> qry(register int x,register int l,register int r,register int L,register int R){
    if(L<=l&&r<=R) return make_pair(mn[x],mx[x]);
    int mid=l+r>>1;
    if(R<=mid) return qry(x<<1,l,mid,L,R);
    else if(L>mid) return qry(x<<1|1,mid+1,r,L,R);
    else{
        pair<int,int> tmp1=qry(x<<1,l,mid,L,R),tmp2=qry(x<<1|1,mid+1,r,L,R);
        return make_pair(min(tmp1.first,tmp2.first),max(tmp1.second,tmp2.second));
    }
}
int mnpre[N],mxnxt[N];
int main()
{
    T=read();
    while(T--){
        n=read();
        for(register int i=1;i<=n;++i) v[i].clear();
        for(register int i=1;i<=n;++i) a[i]=read(),v[a[i]].push_back(i);
        for(register int i=1;i<=n;++i){
            if(!v[i].size()) continue;
            sort(v[i].begin(),v[i].end());
            int tmp=v[i].size();
            for(register int j=0;j<tmp;++j) pre[v[i][j]]=v[i][0],nxt[v[i][j]]=v[i][tmp-1];
        }
        build(1,1,n);
        for(register int i=1;i<=n;++i){
            pair<int,int> tmp=qry(1,1,n,pre[i],i);
            mnpre[i]=tmp.first,mxnxt[i]=tmp.second;
        }
        for(register int i=1;i<=n;++i){
            if(nxt[i]==i){
                int su=mnpre[i],ki=mxnxt[i],cur=pre[i];
                while(su<cur){
                    if(ki>i) break;
                    ki=max(ki,mxnxt[v[a[su]][(int)v[a[su]].size()-1]]);
                    cur=su;
                    su=mnpre[v[a[su]][(int)v[a[su]].size()-1]];
                }
                if(ki<=i) f[i]=f[su-1]+1; else f[i]=0;
            }else f[i]=0;
        }
        ll ans=0;
        for(register int i=1;i<=n;++i) ans+=1ll*f[i];
        write(ans),puts("");
    }
	return 0;
}