#include<stdio.h>
#include<algorithm>
#define bl 174
#define gc getchar_unlocked
#define pc(x) putchar_unlocked(x);
inline void print(int n)
{
int N = n, rev, count = 0;
rev = N;
if (N == 0) { pc('0'); pc('\n'); return ;}
while ((rev % 10) == 0) { count++; rev /= 10;} //obtain the count of the number of 0s
rev = 0;
while (N != 0) { rev = (rev<<3) + (rev<<1) + N % 10; N /= 10;} //store reverse of N in rev
while (rev != 0) { pc(rev % 10 + '0'); rev /= 10;}
while (count--) pc('0');
}
int read_int() {
char c = gc();
while(c<'0' || c>'9') c = gc();
int ret = 0;
while(c>='0' && c<='9') {
ret = 10 * ret + c - 48;
c = gc();
}
return ret;
}
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;
n=read_int();
for(i=0;i<n;i++)
ar[i]=read_int();
m=read_int();
for(i=0;i<m;i++)
{
q[i].l=read_int();
q[i].r=read_int();
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++)
print(ans[i]);
return 0;
}
I2luY2x1ZGU8c3RkaW8uaD4KI2luY2x1ZGU8YWxnb3JpdGhtPgojZGVmaW5lIGJsIDE3NAojZGVmaW5lIGdjIGdldGNoYXJfdW5sb2NrZWQKI2RlZmluZSBwYyh4KSBwdXRjaGFyX3VubG9ja2VkKHgpOwogICAgaW5saW5lIHZvaWQgcHJpbnQoaW50IG4pCiAgICB7CiAgICAgICAgaW50IE4gPSBuLCByZXYsIGNvdW50ID0gMDsKICAgICAgICByZXYgPSBOOwogICAgICAgIGlmIChOID09IDApIHsgcGMoJzAnKTsgcGMoJ1xuJyk7IHJldHVybiA7fQogICAgICAgIHdoaWxlICgocmV2ICUgMTApID09IDApIHsgY291bnQrKzsgcmV2IC89IDEwO30gLy9vYnRhaW4gdGhlIGNvdW50IG9mIHRoZSBudW1iZXIgb2YgMHMKICAgICAgICByZXYgPSAwOwogICAgICAgIHdoaWxlIChOICE9IDApIHsgcmV2ID0gKHJldjw8MykgKyAocmV2PDwxKSArIE4gJSAxMDsgTiAvPSAxMDt9ICAvL3N0b3JlIHJldmVyc2Ugb2YgTiBpbiByZXYKICAgICAgICB3aGlsZSAocmV2ICE9IDApIHsgcGMocmV2ICUgMTAgKyAnMCcpOyByZXYgLz0gMTA7fQogICAgICAgIHdoaWxlIChjb3VudC0tKSBwYygnMCcpOwogICAgfQppbnQgcmVhZF9pbnQoKSB7CiAgY2hhciBjID0gZ2MoKTsKICB3aGlsZShjPCcwJyB8fCBjPic5JykgYyA9IGdjKCk7CiAgaW50IHJldCA9IDA7CiAgd2hpbGUoYz49JzAnICYmIGM8PSc5JykgewogICAgcmV0ID0gMTAgKiByZXQgKyBjIC0gNDg7CiAgICBjID0gZ2MoKTsKICB9CiAgcmV0dXJuIHJldDsKfQp0eXBlZGVmIGxvbmcgbG9uZyBsbDsKc3RydWN0IG5vZGV7CglsbCBsLHIscDsKfXFbMjAwMDA2XTsKbGwgYXJbMzAwMDVdLGNudFsxMDAwMDA2XSxhbnN3ZXI9MCxhbnNbMjAwMDAwNl07CmJvb2wgc29ydGluZyhub2RlIGEsbm9kZSBiKQp7CglpZigoYS5sL2JsKSE9KGIubCkvYmwpCgl7CgkJcmV0dXJuKChhLmwvYmwpPChiLmwvYmwpKTsKCX0KCXJldHVybiAoYS5yPGIucik7CgkKfQp2b2lkIHJlbW92ZShsbCBwKQp7CgljbnRbYXJbcF1dLS07CglpZihjbnRbYXJbcF1dPT0wKQoJewoJCWFuc3dlci0tOwoJfQp9CnZvaWQgYWRkKGxsIHApCnsKCWNudFthcltwXV0rKzsKCWlmKGNudFthcltwXV09PTEpCglhbnN3ZXIrKzsKfQppbnQgbWFpbigpCnsKCXVzaW5nIG5hbWVzcGFjZSBzdGQ7CglsbCBpLG0sbjsKCW49cmVhZF9pbnQoKTsKCWZvcihpPTA7aTxuO2krKykKCWFyW2ldPXJlYWRfaW50KCk7CgltPXJlYWRfaW50KCk7Cglmb3IoaT0wO2k8bTtpKyspCgl7CgkJcVtpXS5sPXJlYWRfaW50KCk7CgkJcVtpXS5yPXJlYWRfaW50KCk7CgkJcVtpXS5sLS07CgkJcVtpXS5yLS07CgkJcVtpXS5wPWk7Cgl9Cglzb3J0KHEscSttLHNvcnRpbmcpOwoJbGwgY2w9MCxjcj0wLHgseTsKCWZvcihpPTA7aTxtO2krKykKCXsKCQl4PXFbaV0ubDsKCQl5PXFbaV0ucjsKCQl3aGlsZShjbDx4KQoJCXsKCQkJcmVtb3ZlKGNsKTsKCQkJY2wrKzsKCQl9CgkJd2hpbGUoY2w+eCkKCQl7CgkJCWFkZChjbC0xKTsKCQkJY2wtLTsKCQl9CgkJd2hpbGUoY3I8PXkpCgkJewoJCQlhZGQoY3IpOwoJCQljcisrOwoJCX0KCQl3aGlsZShjcj55KzEpCgkJewoJCQlyZW1vdmUoY3ItMSk7CgkJCWNyLS07CgkJfQoJCWFuc1txW2ldLnBdPWFuc3dlcjsKCX0KCWZvcihpPTA7aTxtO2krKykKCXByaW50KGFuc1tpXSk7CnJldHVybiAwOwp9