#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
#define mp make_pair
int arr[30005],query[1000005],memo[200005];
class node
{
public:vector< pair< int,pair<int,int> > >link;
};
#define vppi pair< int,pair<int,int> >
node dp[200];
#define gc getchar_unlocked
inline void scanint(int &x)
{
register int c = gc();
x = 0;
for(;(c<48 || c>57);c = gc());
for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
}
inline void add(int i,int *answer)
{
query[arr[i]]++;
if(query[arr[i]]==1) (*answer)++;
}
inline void remove(int i,int *answer)
{
query[arr[i]]--;
if(query[arr[i]]==0) (*answer)--;
}
inline bool compare3( vppi a,vppi b)
{
return a.second.second<b.second.second;
}
int main()
{
int t,n,q,i,j,k,sq,a,b,m;
scanint(n);
for(i=0;i<n;i++) scanint(arr[i]);
sq=ceil( (double)sqrt(n) );
scanint(m);
t=m;
j=0;
while(t--)
{
scanint(a);
scanint(b);
i=(a-1)/sq;
dp[i].link.push_back(mp(j,mp(a-1,b-1)));
j++;
}
for(i=0;i<sq;i++)
{
j=dp[i].link.size();
if(j!=0) sort(dp[i].link.begin(),dp[i].link.end(),compare3);
}
memset(query,0,sizeof(query));
int ans=0;
int currentL=0,currentR=0,L,R;
for(i=0;i<=sq;i++)
{
j=dp[i].link.size();
for(k=0;k<j;k++)
{
L=dp[i].link[k].second.first;
R=dp[i].link[k].second.second;
while( currentL <L)
{
remove(currentL,&ans);
currentL++;
}
while( currentL >L)
{
add(currentL-1,&ans);
currentL--;
}
while( currentR <=R)
{
add(currentR,&ans);
currentR++;
}
while( currentR >R+1)
{
remove(currentR-1,&ans);
currentR--;
}
memo[dp[i].link[k].first]=ans;
}
}
for(i=0;i<m;i++)
{
printf("%d\n",memo[i]);
}
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KI2luY2x1ZGU8YWxnb3JpdGhtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwojZGVmaW5lIG1wIG1ha2VfcGFpcgppbnQgYXJyWzMwMDA1XSxxdWVyeVsxMDAwMDA1XSxtZW1vWzIwMDAwNV07CmNsYXNzIG5vZGUKewoJcHVibGljOnZlY3RvcjwgcGFpcjwgaW50LHBhaXI8aW50LGludD4gPiA+bGluazsKfTsKCiNkZWZpbmUgdnBwaSBwYWlyPCBpbnQscGFpcjxpbnQsaW50PiA+Cm5vZGUgZHBbMjAwXTsKCiNkZWZpbmUgZ2MgZ2V0Y2hhcl91bmxvY2tlZAoKaW5saW5lIHZvaWQgc2NhbmludChpbnQgJngpCnsKICAgIHJlZ2lzdGVyIGludCBjID0gZ2MoKTsKICAgIHggPSAwOwogICAgZm9yKDsoYzw0OCB8fCBjPjU3KTtjID0gZ2MoKSk7CiAgICBmb3IoO2M+NDcgJiYgYzw1ODtjID0gZ2MoKSkge3ggPSAoeDw8MSkgKyAoeDw8MykgKyBjIC0gNDg7fQp9CgppbmxpbmUgdm9pZCBhZGQoaW50IGksaW50ICphbnN3ZXIpCnsKCXF1ZXJ5W2FycltpXV0rKzsKCWlmKHF1ZXJ5W2FycltpXV09PTEpICgqYW5zd2VyKSsrOwp9CgppbmxpbmUgdm9pZCByZW1vdmUoaW50IGksaW50ICphbnN3ZXIpCnsKICAgIHF1ZXJ5W2FycltpXV0tLTsKICAgCWlmKHF1ZXJ5W2FycltpXV09PTApICgqYW5zd2VyKS0tOwoKfQoKaW5saW5lIGJvb2wgY29tcGFyZTMoIHZwcGkgYSx2cHBpIGIpCnsKCXJldHVybiBhLnNlY29uZC5zZWNvbmQ8Yi5zZWNvbmQuc2Vjb25kOwp9CgppbnQgbWFpbigpCnsKCWludCB0LG4scSxpLGosayxzcSxhLGIsbTsKCXNjYW5pbnQobik7Cglmb3IoaT0wO2k8bjtpKyspIHNjYW5pbnQoYXJyW2ldKTsKCXNxPWNlaWwoIChkb3VibGUpc3FydChuKSApOwoJc2NhbmludChtKTsKCXQ9bTsKCWo9MDsKCXdoaWxlKHQtLSkKCXsgCgkgICAKCSAgIAlzY2FuaW50KGEpOwoJICAgCXNjYW5pbnQoYik7CgkJaT0oYS0xKS9zcTsKCSAgICBkcFtpXS5saW5rLnB1c2hfYmFjayhtcChqLG1wKGEtMSxiLTEpKSk7CgkJaisrOwoJCQkKCX0KCQoJZm9yKGk9MDtpPHNxO2krKykKCXsKCQlqPWRwW2ldLmxpbmsuc2l6ZSgpOwoJCWlmKGohPTApIHNvcnQoZHBbaV0ubGluay5iZWdpbigpLGRwW2ldLmxpbmsuZW5kKCksY29tcGFyZTMpOwoJfQoJCgltZW1zZXQocXVlcnksMCxzaXplb2YocXVlcnkpKTsKCQoJaW50IGFucz0wOwoJCgkKCWludCBjdXJyZW50TD0wLGN1cnJlbnRSPTAsTCxSOwoJZm9yKGk9MDtpPD1zcTtpKyspCgl7CgkJaj1kcFtpXS5saW5rLnNpemUoKTsKCQlmb3Ioaz0wO2s8ajtrKyspCgkgICAgewoJICAgIAkKCSAgICAJTD1kcFtpXS5saW5rW2tdLnNlY29uZC5maXJzdDsKCSAgICAJUj1kcFtpXS5saW5rW2tdLnNlY29uZC5zZWNvbmQ7CgkgICAgICAgIHdoaWxlKCBjdXJyZW50TCA8TCkgCgkJICAgIHsKCQkgICAgICAgIHJlbW92ZShjdXJyZW50TCwmYW5zKTsKICAgICAgICAgICAgICAgIGN1cnJlbnRMKys7CiAgICAgICAgICAgIH0KICAgIAoJICAgICAgICB3aGlsZSggY3VycmVudEwgPkwpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGFkZChjdXJyZW50TC0xLCZhbnMpOwogICAgICAgICAgICAgICAgY3VycmVudEwtLTsKICAgICAgICAgICAgfQogICAgICAgICAgICB3aGlsZSggY3VycmVudFIgPD1SKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgIGFkZChjdXJyZW50UiwmYW5zKTsKICAgICAgICAgICAgICAgY3VycmVudFIrKzsKICAgICAgICAgICAgfQogICAgICAgICAgICB3aGlsZSggY3VycmVudFIgPlIrMSkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgcmVtb3ZlKGN1cnJlbnRSLTEsJmFucyk7CiAgICAgICAgICAgICAgICBjdXJyZW50Ui0tOwkKCQkgICAgfQoJCQoJCSAgICBtZW1vW2RwW2ldLmxpbmtba10uZmlyc3RdPWFuczsKCQkgICAgCgkgICAgfQoJICAgIAoJfQoJCglmb3IoaT0wO2k8bTtpKyspIAoJewoJCXByaW50ZigiJWRcbiIsbWVtb1tpXSk7Cgl9Cn0=