#include<cstdio>
#include<algorithm>
using namespace std;
namespace IO{
	const int sz=1<<22;
	char a[sz+5],b[sz+5],*p1=a,*p2=a,*t=b,p[105];
	inline char gc(){
		return p1==p2?(p2=(p1=a)+fread(a,1,sz,stdin),p1==p2?EOF:*p1++):*p1++;
	}
	template<class T> void read(T& x){
		x=0; char c=gc();
		for(;c<'0'||c>'9';c=gc());
		for(;c>='0'&&c<='9';c=gc())
			x=x*10+(c-'0');
	}
	inline void flush(){fwrite(b,1,t-b,stdout),t=b; }
	inline void pc(char x){*t++=x; if(t-b==sz) flush(); }
	template<class T> void write(T x,char c='\n'){
		if(x<0) pc('-'), x=-x;
		if(x==0) pc('0'); int t=0;
		for(;x;x/=10) p[++t]=x%10+'0';
		for(;t;--t) pc(p[t]); pc(c);
	}
	struct F{~F(){flush();}}f;
}
using IO::read;
using IO::write;
const int N=5e5+5;
int n,m,a[N],b[N],nxt[N],ql[N],qr[N],q[N],t[N<<2][2],tag[N<<2],tb[N<<2][2];
long long ans[N],sum[N<<2];
bool cmp(int x,int y){return qr[x]<qr[y];}
void build(int v,int l,int r)
{
	t[v][0]=r-l+1;
	if(l==r)return;
	int mid=l+r>>1;
	build(v<<1,l,mid);
	build(v<<1|1,mid+1,r);
}
void pt(int v,int t0,int t1,int tt)
{
	sum[v]+=1ll*t[v][0]*t1+1ll*t[v][1]*t0;
	if(tt)swap(t[v][0],t[v][1]);
	tb[v][tag[v]]+=t0;
	tb[v][tag[v]^1]+=t1;
	tag[v]^=tt;
}
void push(int v)
{
	pt(v<<1,tb[v][0],tb[v][1],tag[v]);
	pt(v<<1|1,tb[v][0],tb[v][1],tag[v]);
	tag[v]=tb[v][0]=tb[v][1]=0;
}
void upt(int v,int l,int r,int x,int y,int z)
{
	if(l>=x&&r<=y)return pt(v,!z,z,z),void();
	push(v);
	int mid=l+r>>1;
	if(x<=mid)upt(v<<1,l,mid,x,y,z);
	if(mid<y)upt(v<<1|1,mid+1,r,x,y,z);
	sum[v]=sum[v<<1]+sum[v<<1|1];
	t[v][0]=t[v<<1][0]+t[v<<1|1][0];
	t[v][1]=t[v<<1][1]+t[v<<1|1][1];
}
long long que(int v,int l,int r,int x,int y)
{
	if(l>=x&&r<=y)return sum[v];
	push(v);
	int mid=l+r>>1;
	long long res=0;
	if(x<=mid)res+=que(v<<1,l,mid,x,y);
	if(mid<y)res+=que(v<<1|1,mid+1,r,x,y);
	return res;
}
int main()
{
	read(n);
	for(int i=1;i<=n;i++)read(a[i]),nxt[i]=b[a[i]],b[a[i]]=i;
	read(m);
	for(int i=1;i<=m;i++)read(ql[i]),read(qr[i]),q[i]=i;
	sort(q+1,q+1+m,cmp);
	build(1,1,n);
	for(int i=1,j=1;i<=n;i++)
	{
		upt(1,1,n,nxt[i]+1,i,1);
		if(nxt[i])upt(1,1,n,1,nxt[i],0);
		for(;j<=m&&qr[q[j]]==i;j++)ans[q[j]]=que(1,1,n,ql[q[j]],i);
	}
	for(int i=1;i<=m;i++)write(ans[i]);
	return 0;
}