#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <cmath>
using namespace std;
typedef long long int LL;
struct node{
int l;
int r;
int id;
}u[311111];
int z;
bool cool(node a,node b)
{
if(a.l/z<b.l/z)
return true;
if(a.l/z>b.l/z)
return false;
return a.r<b.r;
}
int cnt[1111111];
int ans[311111];
int v[311111];
int main()
{
//ios_base:: sync_with_stdio(false); cin.tie(0);
// freopen("input.in","r",stdin);
int n;cin>>n;
int fuk=0;
z=sqrt(n);
// vector<int>v(n);
for(int i=0;i<n;i++)
scanf("%d",&v[i]);
int q;cin>>q;for(int i=0;i<q;i++)
{
int l,r;
scanf("%d %d",&l,&r);
node tmp;
tmp.l=l-1;
tmp.r=r-1;
tmp.id=i;
u[i]=tmp;
}
sort(u,u+q,cool);
int st=0,e=0;fuk=1;cnt[v[0]]++;
for(int i=0;i<q;i++)
{
int l=u[i].l;
int r=u[i].r;
// cout<<l<<" "<<r<<" "<<st<<" "<<e<<" "<<fuk<<endl;
while(st<l)
{
cnt[v[st]]--;
if(cnt[v[st]]==0)
fuk--;
st++;
}
while(st>l)
{
st--;
cnt[v[st]]++;
if(cnt[v[st]]==1)
fuk++;
}
while(e<r)
{
e++;
cnt[v[e]]++;
if(cnt[v[e]]==1)
fuk++;
}
while(e>r)
{
cnt[v[e]]--;
if(cnt[v[e]]==0)
fuk--;
e--;
}
ans[u[i].id]=fuk;
}
for(int i=0;i<q;i++)
printf("%d\n",ans[i]);
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8dXRpbGl0eT4KI2luY2x1ZGUgPGNtYXRoPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwp0eXBlZGVmIGxvbmcgbG9uZyBpbnQgTEw7CgpzdHJ1Y3Qgbm9kZXsKICBpbnQgbDsKICBpbnQgcjsKICBpbnQgaWQ7Cn11WzMxMTExMV07CgppbnQgejsKYm9vbCBjb29sKG5vZGUgYSxub2RlIGIpCnsKICAgICBpZihhLmwvejxiLmwveikKICAgICAgICByZXR1cm4gdHJ1ZTsKICAgICBpZihhLmwvej5iLmwveikKICAgICAgICByZXR1cm4gZmFsc2U7CiAgICAgcmV0dXJuIGEucjxiLnI7Cn0KIGludCBjbnRbMTExMTExMV07CiBpbnQgYW5zWzMxMTExMV07CiBpbnQgdlszMTExMTFdOwoKaW50IG1haW4oKQp7CgogICAgIC8vaW9zX2Jhc2U6OiBzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOyBjaW4udGllKDApOwogICAgICAKICAgCiAgICAvLyBmcmVvcGVuKCJpbnB1dC5pbiIsInIiLHN0ZGluKTsKICAgICAgICAKICAgICAgICBpbnQgbjtjaW4+Pm47CiAgICAgICAgaW50IGZ1az0wOwogICAgICAgIHo9c3FydChuKTsKICAgICAgLy8gIHZlY3RvcjxpbnQ+dihuKTsKICAgICAgICAKICAgICAgICBmb3IoaW50IGk9MDtpPG47aSsrKQogICAgICAgICAgICAgICAgc2NhbmYoIiVkIiwmdltpXSk7CiAgICAgICAgICAgICAgICAgICAgCiAgICAgICAgaW50IHE7Y2luPj5xO2ZvcihpbnQgaT0wO2k8cTtpKyspCiAgICAgICAgewogICAgICAgICAgICAgaW50IGwscjsKICAgICAgICAgICAgIHNjYW5mKCIlZCAlZCIsJmwsJnIpOwogICAgICAgICAgICAgbm9kZSB0bXA7CiAgICAgICAgICAgICB0bXAubD1sLTE7CiAgICAgICAgICAgICB0bXAucj1yLTE7CiAgICAgICAgICAgICB0bXAuaWQ9aTsKICAgICAgICAgICAgIHVbaV09dG1wOwogICAgICAgIH0KCiAgICAgICAgIHNvcnQodSx1K3EsY29vbCk7CgogICAgICAgICBpbnQgc3Q9MCxlPTA7ZnVrPTE7Y250W3ZbMF1dKys7CgogICAgICAgIGZvcihpbnQgaT0wO2k8cTtpKyspCiAgICAgICAgewogICAgICAgICAgICBpbnQgbD11W2ldLmw7CiAgICAgICAgICAgIGludCByPXVbaV0ucjsKICAgICAgICAgICAvLyBjb3V0PDxsPDwiICI8PHI8PCIgIjw8c3Q8PCIgIjw8ZTw8IiAiPDxmdWs8PGVuZGw7CiAgICAgICAgICAgIAogICAgICAgICAgICB3aGlsZShzdDxsKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBjbnRbdltzdF1dLS07CiAgICAgICAgICAgICAgICBpZihjbnRbdltzdF1dPT0wKQogICAgICAgICAgICAgICAgIGZ1ay0tOwogICAgICAgICAgICAgICAgIHN0Kys7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgd2hpbGUoc3Q+bCkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgIHN0LS07CiAgICAgICAgICAgICAgICAgY250W3Zbc3RdXSsrOwogICAgICAgICAgICAgICAgIGlmKGNudFt2W3N0XV09PTEpCiAgICAgICAgICAgICAgICAgZnVrKys7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgd2hpbGUoZTxyKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBlKys7CiAgICAgICAgICAgICAgICBjbnRbdltlXV0rKzsKICAgICAgICAgICAgICAgIGlmKGNudFt2W2VdXT09MSkKICAgICAgICAgICAgICAgIGZ1aysrOwogICAgICAgICAgICB9CiAgICAgICAgICAgIHdoaWxlKGU+cikKICAgICAgICAgICAgewogICAgICAgICAgICAgICBjbnRbdltlXV0tLTsKICAgICAgICAgICAgICAgaWYoY250W3ZbZV1dPT0wKQogICAgICAgICAgICAgICBmdWstLTsKICAgICAgICAgICAgICAgZS0tOwogICAgICAgICAgICB9ICAgICAgICAgICAgCiAgICAgICAgICAgIGFuc1t1W2ldLmlkXT1mdWs7CiAgICAgICAgfQoKICAgICAgICBmb3IoaW50IGk9MDtpPHE7aSsrKQogICAgICAgICAgICBwcmludGYoIiVkXG4iLGFuc1tpXSk7CgogICAgIHJldHVybiAwOwp9CgoK