已经按照题解的方法卡常了，有一个点 3.13s 的，求卡/kk

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define N 1000006
using namespace std;
inline int read()
{
    register int ret=0,bas=1;register char ch=getchar_unlocked();
    while(!isdigit(ch)&&ch!='-')ch=getchar_unlocked();
    while(isdigit(ch))ret=(ret<<3)+(ret<<1)+(ch^48),ch=getchar_unlocked();
    return bas*ret;
}
inline void print(int k)
{
    register int nnum[20],tp=0;
    while(k)nnum[++tp]=k%10,k/=10;
    if(!tp)nnum[++tp]=0;
    for(int i=tp;i;i--)putchar(nnum[i]^48);
}
int n,m,a[N],lst[N],ans[N];
struct Matrix
{
    int num00,num01,num02;
    int num10,num11,num12;
    int num22;
}B0,B1,B2,B3,tree[N<<2],tag[N<<2];
struct Segment{int l,r,id;}b[N];
inline bool operator <(const Segment x,const Segment y){return x.r^y.r?x.r<y.r:x.l<y.l;}
inline Matrix operator +(const Matrix x,const Matrix y)
{
	Matrix ret;
	ret={x.num00+y.num00,x.num01+y.num01,x.num02+y.num02};
	return ret;
}
inline Matrix operator *(const Matrix x,const Matrix y)
{
	Matrix ret;
	ret.num00=x.num00*y.num00+x.num01*y.num10;
	ret.num01=x.num00*y.num01+x.num01*y.num11;
	ret.num02=x.num00*y.num02+x.num01*y.num12+x.num02*y.num22;
	ret.num10=x.num10*y.num00+x.num11*y.num10;
	ret.num11=x.num10*y.num01+x.num11*y.num11;
	ret.num12=x.num10*y.num02+x.num11*y.num12+x.num12*y.num22;
	ret.num22=x.num22*y.num22;
	return ret;
}
bool operator ==(const Matrix x,const Matrix y)
{
    if(x.num00!=y.num00)return 0;
    if(x.num01!=y.num01)return 0;
    if(x.num02!=y.num02)return 0;
    if(x.num10!=y.num10)return 0;
    if(x.num11!=y.num11)return 0;
    if(x.num12!=y.num12)return 0;
    if(x.num22!=y.num22)return 0;
    return 1;
}
inline void Matrix_init()
{
	B0.num00=1;
	B1.num01=B1.num02=B1.num10=B1.num22=1;
	B2.num00=B2.num11=B2.num12=B2.num22=1;
	B3.num00=B3.num11=B3.num22=1;
}
inline void build(int p,int l,int r)
{
	tag[p]=B3;
	if(l==r){tree[p]=B0;return;}
	register int mid=l+r>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	tree[p]=tree[p<<1]+tree[p<<1|1];
}
inline void addtag(int p,Matrix x)
{
	tree[p]=tree[p]*x;
	tag[p]=tag[p]*x;
}
inline void push_down(int p)
{
	if(tag[p]==B3);
	else
    {
        addtag(p<<1,tag[p]);
        addtag(p<<1|1,tag[p]);
        tag[p]=B3;
    }
}
inline void update(int p,int l,int r,int L,int R,Matrix x)
{
	if(L<=l&&r<=R){addtag(p,x);return;}
	push_down(p);
	register int mid=l+r>>1;
	if(L<=mid)update(p<<1,l,mid,L,R,x);
	if(R>mid)update(p<<1|1,mid+1,r,L,R,x);
	tree[p]=tree[p<<1]+tree[p<<1|1];
}
inline int query(int p,int l,int r,int L,int R)
{
	if(L<=l&&r<=R)return tree[p].num02;
	push_down(p);
	register int mid=l+r>>1;
	if(R<=mid)return query(p<<1,l,mid,L,R);
	if(L>mid)return query(p<<1|1,mid+1,r,L,R);
	return query(p<<1,l,mid,L,R)+query(p<<1|1,mid+1,r,L,R);
}
main()
{
	Matrix_init();
	n=read();
	for(register int i=1;i<=n;i=-~i)a[i]=read();
	build(1,1,n);
	m=read();
	for(register int i=1;i<=m;i=-~i)b[i]={read(),read(),i};
	sort(b+1,b+1+m);
	register int nowpos=0;
	for(register int i=1;i<=n;i=-~i)
	{
		update(1,1,n,lst[a[i]]+1,i,B1);
		if(lst[a[i]])update(1,1,n,1,lst[a[i]],B2);
		lst[a[i]]=i;
		while(b[nowpos+1].r==i)nowpos=-~nowpos,ans[b[nowpos].id]=query(1,1,n,b[nowpos].l,i);
	}
	for(register int i=1;i<=m;i=-~i)print(ans[i]),putchar('\n');
	return 0;
}