#include<stdio.h>
#include<algorithm>
#define bl 174
typedef long long ll;
struct node{
ll l,r,p;
}q[200006];
ll ar[30005],cnt[1000006],answer=0,ans[2000006];
bool sorting(node a,node b)
{
if((a.l/bl)!=(b.l)/bl)
{
return((a.l/bl)<(b.l/bl));
}
return (a.r<b.r);
}
void remove(ll p)
{
cnt[ar[p]]--;
if(cnt[ar[p]]==0)
{
answer--;
}
}
void add(ll p)
{
cnt[ar[p]]++;
if(cnt[ar[p]]==1)
answer++;
}
int main()
{
using namespace std;
ll i,m,n;
scanf("%lld",&n);
for(i=0;i<n;i++)
scanf("%lld",&ar[i]);
scanf("%lld",&m);
for(i=0;i<m;i++)
{
scanf("%lld%lld",&q[i].l,&q[i].r);
q[i].l--;
q[i].r--;
q[i].p=i;
}
sort(q,q+m,sorting);
ll cl=0,cr=0,x,y;
for(i=0;i<m;i++)
{
x=q[i].l;
y=q[i].r;
while(cl<x)
{
remove(cl);
cl++;
}
while(cl>x)
{
add(cl-1);
cl--;
}
while(cr<=y)
{
add(cr);
cr++;
}
while(cr>y+1)
{
remove(cr-1);
cr--;
}
ans[q[i].p]=answer;
}
for(i=0;i<m;i++)
printf("%lld\n",ans[i]);
return 0;
}
I2luY2x1ZGU8c3RkaW8uaD4KI2luY2x1ZGU8YWxnb3JpdGhtPgojZGVmaW5lIGJsIDE3NAp0eXBlZGVmIGxvbmcgbG9uZyBsbDsKc3RydWN0IG5vZGV7CglsbCBsLHIscDsKfXFbMjAwMDA2XTsKbGwgYXJbMzAwMDVdLGNudFsxMDAwMDA2XSxhbnN3ZXI9MCxhbnNbMjAwMDAwNl07CmJvb2wgc29ydGluZyhub2RlIGEsbm9kZSBiKQp7CglpZigoYS5sL2JsKSE9KGIubCkvYmwpCgl7CgkJcmV0dXJuKChhLmwvYmwpPChiLmwvYmwpKTsKCX0KCXJldHVybiAoYS5yPGIucik7CgkKfQp2b2lkIHJlbW92ZShsbCBwKQp7CgljbnRbYXJbcF1dLS07CglpZihjbnRbYXJbcF1dPT0wKQoJewoJCWFuc3dlci0tOwoJfQp9CnZvaWQgYWRkKGxsIHApCnsKCWNudFthcltwXV0rKzsKCWlmKGNudFthcltwXV09PTEpCglhbnN3ZXIrKzsKfQppbnQgbWFpbigpCnsKCXVzaW5nIG5hbWVzcGFjZSBzdGQ7CglsbCBpLG0sbjsKCXNjYW5mKCIlbGxkIiwmbik7Cglmb3IoaT0wO2k8bjtpKyspCglzY2FuZigiJWxsZCIsJmFyW2ldKTsKCXNjYW5mKCIlbGxkIiwmbSk7Cglmb3IoaT0wO2k8bTtpKyspCgl7CgkJc2NhbmYoIiVsbGQlbGxkIiwmcVtpXS5sLCZxW2ldLnIpOwoJCXFbaV0ubC0tOwoJCXFbaV0uci0tOwoJCXFbaV0ucD1pOwoJfQoJc29ydChxLHErbSxzb3J0aW5nKTsKCWxsIGNsPTAsY3I9MCx4LHk7Cglmb3IoaT0wO2k8bTtpKyspCgl7CgkJeD1xW2ldLmw7CgkJeT1xW2ldLnI7CgkJd2hpbGUoY2w8eCkKCQl7CgkJCXJlbW92ZShjbCk7CgkJCWNsKys7CgkJfQoJCXdoaWxlKGNsPngpCgkJewoJCQlhZGQoY2wtMSk7CgkJCWNsLS07CgkJfQoJCXdoaWxlKGNyPD15KQoJCXsKCQkJYWRkKGNyKTsKCQkJY3IrKzsKCQl9CgkJd2hpbGUoY3I+eSsxKQoJCXsKCQkJcmVtb3ZlKGNyLTEpOwoJCQljci0tOwoJCX0KCQlhbnNbcVtpXS5wXT1hbnN3ZXI7Cgl9Cglmb3IoaT0wO2k8bTtpKyspCglwcmludGYoIiVsbGRcbiIsYW5zW2ldKTsKcmV0dXJuIDA7Cn0=