//Mo's Algorithm WTF lol
#include<stdio.h>
#include<list>
#include<algorithm>
#define gc getchar_unlocked
using namespace std;
int visited[1000001];
int A[30001];
pair < int , pair <int , int > > Q[200000];
int queries[200000];
int fastscan();
inline void printint(int a)
{
char s[11];
int t = -1;
do{
s[++t] = a % 10 + '0';
a /= 10;
}while(a > 0);
while(t >= 0)putchar_unlocked(s[t--]);
putchar_unlocked('\n');
}
bool cmp(pair < int , pair <int , int > > a , pair < int , pair <int , int > > b);
int main()
{
int n,i,j=-1,q,qe,qr,L=-1,R=-1,ans=0,k,idx;
n=fastscan();
for(i=0;i<n;i++)
A[i]=fastscan();
q=fastscan();
for(i=0;i<q;i++)
{
qe=fastscan();
qr=fastscan();
Q[i]=make_pair(qe-1,make_pair(qr-1,i));
}
sort(Q,Q+q,cmp);
for(i=0;i<q;i++)
{
j=Q[i].first;
k=Q[i].second.first;
idx=Q[i].second.second;
if(L==-1)
{
L=j;
R=k;
for(int it=j;it<=k;it++)
{
visited[A[it]]++;
if(visited[A[it]]==1)
ans++;
}
}
while(L<j)
{
visited[A[L]]--;
if(visited[A[L]]==0)
ans--;
L++;
}
while(L>j)
{
L--;
visited[A[L]]++;
if(visited[A[L]]==1)
ans++;;
}
while(R<k)
{
R++;
visited[A[R]]++;
if(visited[A[R]]==1)
ans++;
}
while(R>k)
{
visited[A[R]]--;
if(visited[A[R]]==0)
ans--;
R--;
}
queries[idx]=ans;
}
for(i=0;i<q;i++)
printint(queries[i]);
return 0;
}
int fastscan()
{
register int n=0;
char ch=gc();
for(;(ch<48||ch>57);ch=gc())
;
for(;(ch>47&&ch<58);ch=gc())
n=(n<<3)+(n<<1)+ch-48;
/* for(;ch>47 && ch<58;ch = gc())
{
x = (x<<1) + (x<<3) + ch - 48;
}*/
return n;
}
bool cmp(pair < int , pair <int , int > > a , pair < int , pair <int , int > > b)
{
if(a.first<b.first)
return true;
else if(a.first==b.first)
{
if(a.second<b.second)
return true;
else
return false;
}
else
return false;
}
Ly9NbydzIEFsZ29yaXRobSBXVEYgbG9sCiNpbmNsdWRlPHN0ZGlvLmg+CiNpbmNsdWRlPGxpc3Q+CiNpbmNsdWRlPGFsZ29yaXRobT4KI2RlZmluZSBnYyBnZXRjaGFyX3VubG9ja2VkCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmludCB2aXNpdGVkWzEwMDAwMDFdOwppbnQgQVszMDAwMV07CnBhaXIgPCBpbnQgLCBwYWlyIDxpbnQgLCBpbnQgPiA+IFFbMjAwMDAwXTsKaW50IHF1ZXJpZXNbMjAwMDAwXTsKaW50IGZhc3RzY2FuKCk7CmlubGluZSB2b2lkIHByaW50aW50KGludCBhKQp7CiAgICBjaGFyIHNbMTFdOwogICAgaW50IHQgPSAtMTsKICAgIGRvewogICAgc1srK3RdID0gYSAlIDEwICsgJzAnOwogICAgYSAvPSAxMDsKfXdoaWxlKGEgPiAwKTsKICAgIHdoaWxlKHQgPj0gMClwdXRjaGFyX3VubG9ja2VkKHNbdC0tXSk7CiAgICBwdXRjaGFyX3VubG9ja2VkKCdcbicpOwp9CmJvb2wgY21wKHBhaXIgPCBpbnQgLCBwYWlyIDxpbnQgLCBpbnQgPiA+IGEgLCBwYWlyIDwgaW50ICwgcGFpciA8aW50ICwgaW50ID4gPiBiKTsKaW50IG1haW4oKQp7CiAgICBpbnQgbixpLGo9LTEscSxxZSxxcixMPS0xLFI9LTEsYW5zPTAsayxpZHg7CiAgICBuPWZhc3RzY2FuKCk7CiAgICBmb3IoaT0wO2k8bjtpKyspCiAgICAgICAgQVtpXT1mYXN0c2NhbigpOwogICAgcT1mYXN0c2NhbigpOwogICAgZm9yKGk9MDtpPHE7aSsrKQogICAgewogICAgICAgIHFlPWZhc3RzY2FuKCk7CiAgICAgICAgcXI9ZmFzdHNjYW4oKTsKICAgICAgICBRW2ldPW1ha2VfcGFpcihxZS0xLG1ha2VfcGFpcihxci0xLGkpKTsKICAgIH0KICAgIHNvcnQoUSxRK3EsY21wKTsKICAgIGZvcihpPTA7aTxxO2krKykKICAgIHsKICAgICAgICBqPVFbaV0uZmlyc3Q7CiAgICAgICAgaz1RW2ldLnNlY29uZC5maXJzdDsKICAgICAgICBpZHg9UVtpXS5zZWNvbmQuc2Vjb25kOwogICAgICAgIGlmKEw9PS0xKQogICAgICAgIHsKICAgICAgICAgICAgTD1qOwogICAgICAgICAgICBSPWs7CiAgICAgICAgICAgIGZvcihpbnQgaXQ9ajtpdDw9aztpdCsrKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICB2aXNpdGVkW0FbaXRdXSsrOwogICAgICAgICAgICAgICAgaWYodmlzaXRlZFtBW2l0XV09PTEpCiAgICAgICAgICAgICAgICAgICAgYW5zKys7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgd2hpbGUoTDxqKQogICAgICAgIHsKICAgICAgICAgICAgdmlzaXRlZFtBW0xdXS0tOwogICAgICAgICAgICBpZih2aXNpdGVkW0FbTF1dPT0wKQogICAgICAgICAgICAgICAgYW5zLS07CiAgICAgICAgICAgIEwrKzsKICAgICAgICB9CiAgICAgICAgd2hpbGUoTD5qKQogICAgICAgIHsKICAgICAgICAgICAgTC0tOwogICAgICAgICAgICB2aXNpdGVkW0FbTF1dKys7CiAgICAgICAgICAgIGlmKHZpc2l0ZWRbQVtMXV09PTEpCiAgICAgICAgICAgICAgICBhbnMrKzs7CgogICAgICAgIH0KICAgICAgICB3aGlsZShSPGspCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIFIrKzsKICAgICAgICAgICAgICAgIHZpc2l0ZWRbQVtSXV0rKzsKICAgICAgICAgICAgICAgIGlmKHZpc2l0ZWRbQVtSXV09PTEpCiAgICAgICAgICAgICAgICAgICAgYW5zKys7CiAgICAgICAgICAgIH0KICAgICAgICB3aGlsZShSPmspCiAgICAgICAgewogICAgICAgICAgICB2aXNpdGVkW0FbUl1dLS07CiAgICAgICAgICAgIGlmKHZpc2l0ZWRbQVtSXV09PTApCiAgICAgICAgICAgICAgICBhbnMtLTsKICAgICAgICAgICAgUi0tOwogICAgICAgIH0KICAgICAgICBxdWVyaWVzW2lkeF09YW5zOwogICAgfQogICAgZm9yKGk9MDtpPHE7aSsrKQogICAgICAgIHByaW50aW50KHF1ZXJpZXNbaV0pOwogICAgcmV0dXJuIDA7Cn0KaW50IGZhc3RzY2FuKCkKewogICAgcmVnaXN0ZXIgaW50IG49MDsKICAgIGNoYXIgY2g9Z2MoKTsKICAgIGZvcig7KGNoPDQ4fHxjaD41Nyk7Y2g9Z2MoKSkKICAgICAgICA7CiAgICBmb3IoOyhjaD40NyYmY2g8NTgpO2NoPWdjKCkpCiAgICAgICAgbj0objw8MykrKG48PDEpK2NoLTQ4OwogICAvKiBmb3IoO2NoPjQ3ICYmIGNoPDU4O2NoID0gZ2MoKSkKICAgIHsKICAgICAgICB4ID0gKHg8PDEpICsgKHg8PDMpICsgY2ggLSA0ODsKICAgIH0qLwogICAgcmV0dXJuIG47Cgp9Cgpib29sIGNtcChwYWlyIDwgaW50ICwgcGFpciA8aW50ICwgaW50ID4gPiBhICwgcGFpciA8IGludCAsIHBhaXIgPGludCAsIGludCA+ID4gYikKewogICAgaWYoYS5maXJzdDxiLmZpcnN0KQogICAgICAgIHJldHVybiB0cnVlOwogICAgZWxzZSBpZihhLmZpcnN0PT1iLmZpcnN0KQogICAgewogICAgICAgIGlmKGEuc2Vjb25kPGIuc2Vjb25kKQogICAgICAgICAgICByZXR1cm4gdHJ1ZTsKICAgICAgICBlbHNlCiAgICAgICAgICAgIHJldHVybiBmYWxzZTsKICAgIH0KICAgIGVsc2UKICAgICAgICByZXR1cm4gZmFsc2U7Cn0K