#define N 1000001
max(a,b){return a>b?a:b;}
#include<stdio.h>
int n,pre[N],a[N],pos[N];
int Max[N][30];
int query(int x,int logg,int start,int sx){
  //printf("query:%d %d %d (sx:%d)\n",x,logg,start,sx);
  if(x+(1<<logg)-1<start) return 0;
  if(Max[x][logg]<sx) 
    return x+(1<<logg)-1-start+1;
  if(logg){
    if(x+(1<<logg-1)-1<start) 
      return query(x+(1<<logg-1),logg-1,start,sx);
    else return query(x,logg-1,start,sx)+query(x+(1<<logg-1),logg-1,x+(1<<logg-1),sx);//分情况
  }
  else return 0;//
}
main(){
  scanf("%d",&n);
  for(int i=1;i<=n;++i){
    scanf("%d",a+i);
    pre[i]=pos[a[i]];
    pos[a[i]]=i;
    Max[i][0]=pre[i];
  }
  const int right=(int)(log2(n));
  for(int i=1;i<=right;++i)
    for(int j=1;j+(1<<i)-1<=n;++j)
      Max[j][i]=max(Max[j][i-1],Max[j+(1<<i-1)][i-1]);
  /*for(int i=0;i<=right;++i){
    printf("log:%d\n",i);
    for(int j=1;j+(1<<i)-1<=n;++j)
      printf("max in [%d,%d] is %d\n",j,j+(1<<i)-1,Max[j][i]);
  }*/
  int m;
  scanf("%d",&m);
  for(int l,r,top,x=1,y,ans=0,sx;m--;ans=0,x=1){
    scanf("%d%d",&l,&r);
    top=right,sx=l;
    while(x<=r){
      //printf("cal:x=%d r=%d\n",x,r);
      while(x+(1<<top)-1>r)--top;
      //printf("%d %d %d %d\n",x,x+(1<<top)-1,top,l);
      ans+=query(x,top,l,sx);
      //printf("aqury_done:ans=%d\n",ans);
      l=x=x+(1<<top);
    }
    printf("%d\n",ans);
  }
}