#include<bits/stdc++.h>
#define N 1000005
#define ll long long
#define ri register
#pragma G++ optimize("Ofast","-funroll-loops","-fdelete-null-pointer-checks")
#pragma G++ target("ssse3","sse3","sse2","sse","avx2","avx")
using namespace std;
 int a[N],ans[N],pos[N],n,m,res,cnt[N],t,sum;
struct node{
	 int l,r,id;
}k[N];
bool cmp(node a,node b)
{
    return (pos[a.l]^pos[b.l])?pos[a.l]<pos[b.l]:((pos[a.l]&1)?a.r<b.r:a.r>b.r);
} 

inline int read()
{
	char ch=getchar();int x=0;bool f=false;
	while((ch>'9'||ch<'0')) ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-48,ch=getchar();
	return f?-x:x;
}
void write(int x)        
{             
    if(x>9) write(x/10);        
    putchar(x%10+'0');                
}    
int main(void)
{
	n=read();
	ri int siz=sqrt(n);
	for(ri int i=1;i<=n;i++)
	{
		a[i]=read();
		pos[i]=i/siz;
	}
	m=read();
	for(ri int i=1;i<=m;i++)
	{
		k[i].l=read(),k[i].r=read(); 
		k[i].id=i;
	}
	sort(k+1,k+m+1,cmp);
	int l=1,r=0;
	for(ri int i=1;i<=m;i++)
	{
		while(k[i].l<l) sum+=!cnt[a[--l]]++;
		while(k[i].r>r) sum+=!cnt[a[++r]]++;
		while(k[i].l>l) sum-=!--cnt[a[l++]];
		while(k[i].r<r) sum-=!--cnt[a[r--]];
		ans[k[i].id]=sum;
	}
	for(ri int i=1;i<=m;i++){
		write(ans[i]);
		putchar('\n');
	}	
}