#include<bits/stdc++.h>
#define LL long long int
#define s(a) scanf("%d",&a)
#define sl(a) scanf("%lld",&a)
#define ss(a) scanf("%s",a)
#define w(t) while(t--)
#define f(i,n) for(i=0;i<n;i++)
#define fd(i,n) for(i=n-1;i>=0;i--)
#define p(a) printf("%d",a)
#define pl(a) printf("%lld",a)
#define ps(a) printf("%s",a)
#define pc(a) printf("%c",a)
#define ent printf("\n")
#define mod 1000000007
#define PI 3.14159265
#define gs getline(cin,s)
#define pb push_back
#define mp make_pair
#define INF 1e18
using namespace std;
unordered_map<int,int> pos;
int ar[300005];
int tree[16*300000+5];
int lft[16*300000+5];
int rht[16*300000+5];
int root[600005];
int rt[300005];
int idx;
inline void build(int node,int start,int end)
{
if(start==end)
{
tree[node]=0;
return;
}
lft[node]=idx++;
rht[node]=idx++;
int mid=(start+end)/2;
build(lft[node],start,mid);
build(rht[node],mid+1,end);
tree[node]=0;
}
inline int update(int node,int start,int end,int pos,int val)
{
int x;
x=idx++;
if(start==end)
{
tree[x]=val;
return x;
}
lft[x]=lft[node];
rht[x]=rht[node];
int mid=(start+end)/2;
if(pos<=mid)
lft[x]=update(lft[x],start,mid,pos,val);
else
rht[x]=update(rht[x],mid+1,end,pos,val);
tree[x]=tree[lft[x]]+tree[rht[x]];
return x;
}
inline int query(int node,int start,int end,int l,int r)
{
if(start>r || end<l)
return 0;
else if(start>=l && end<=r)
return tree[node];
int mid=(start+end)/2;
int q1=query(lft[node],start,mid,l,r);
int q2=query(rht[node],mid+1,end,l,r);
return (q1+q2);
}
int main()
{
std:ios_base::sync_with_stdio(false);
int n;
s(n);
int i;
idx=0;
root[0]=0;
build(0,1,n);
int t=1;
for(i=1;i<=n;i++)
{
s(ar[i]);
int k=pos[ar[i]];
if(k!=0)
{
root[t]=update(root[t-1],1,n,k,0);
t++;
root[t]=update(root[t-1],1,n,i,1);
t++;
}
else
{
root[t]=update(root[t-1],1,n,i,1);
t++;
}
rt[i]=t-1;
pos[ar[i]]=i;
}
int m;
s(m);
while(m--)
{
int a,b;
s(a);
s(b);
p(query(root[rt[b]],1,n,a,b));
ent;
}
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KI2RlZmluZSBMTCBsb25nIGxvbmcgaW50CiNkZWZpbmUgcyhhKSBzY2FuZigiJWQiLCZhKQojZGVmaW5lIHNsKGEpIHNjYW5mKCIlbGxkIiwmYSkKI2RlZmluZSBzcyhhKSBzY2FuZigiJXMiLGEpCiNkZWZpbmUgdyh0KSB3aGlsZSh0LS0pCiNkZWZpbmUgZihpLG4pIGZvcihpPTA7aTxuO2krKykKI2RlZmluZSBmZChpLG4pIGZvcihpPW4tMTtpPj0wO2ktLSkKI2RlZmluZSBwKGEpIHByaW50ZigiJWQiLGEpCiNkZWZpbmUgcGwoYSkgcHJpbnRmKCIlbGxkIixhKQojZGVmaW5lIHBzKGEpIHByaW50ZigiJXMiLGEpCiNkZWZpbmUgcGMoYSkgcHJpbnRmKCIlYyIsYSkKI2RlZmluZSBlbnQgcHJpbnRmKCJcbiIpCiNkZWZpbmUgbW9kIDEwMDAwMDAwMDcKI2RlZmluZSBQSSAzLjE0MTU5MjY1CiNkZWZpbmUgZ3MgZ2V0bGluZShjaW4scykKI2RlZmluZSBwYiBwdXNoX2JhY2sKI2RlZmluZSBtcCBtYWtlX3BhaXIKI2RlZmluZSBJTkYgMWUxOAogCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiAKdW5vcmRlcmVkX21hcDxpbnQsaW50PiBwb3M7CmludCBhclszMDAwMDVdOwppbnQgdHJlZVsxNiozMDAwMDArNV07CmludCBsZnRbMTYqMzAwMDAwKzVdOwppbnQgcmh0WzE2KjMwMDAwMCs1XTsKaW50IHJvb3RbNjAwMDA1XTsKaW50IHJ0WzMwMDAwNV07CmludCBpZHg7CiAKaW5saW5lIHZvaWQgYnVpbGQoaW50IG5vZGUsaW50IHN0YXJ0LGludCBlbmQpCnsKICAgIGlmKHN0YXJ0PT1lbmQpCiAgICAgICAgewogICAgICAgICAgICB0cmVlW25vZGVdPTA7CiAgICAgICAgICAgIHJldHVybjsKICAgICAgICB9CiAgICAgICAgbGZ0W25vZGVdPWlkeCsrOwogICAgICAgIHJodFtub2RlXT1pZHgrKzsKICAgICAgICBpbnQgbWlkPShzdGFydCtlbmQpLzI7CiAgICAgICAgYnVpbGQobGZ0W25vZGVdLHN0YXJ0LG1pZCk7CiAgICAgICAgYnVpbGQocmh0W25vZGVdLG1pZCsxLGVuZCk7CiAgICAgICAgdHJlZVtub2RlXT0wOwp9CiAKaW5saW5lIGludCB1cGRhdGUoaW50IG5vZGUsaW50IHN0YXJ0LGludCBlbmQsaW50IHBvcyxpbnQgdmFsKQp7CiAgICBpbnQgeDsKICAgIHg9aWR4Kys7CiAgICBpZihzdGFydD09ZW5kKQogICAgewogICAgICAgIHRyZWVbeF09dmFsOwogICAgICAgIHJldHVybiB4OwogICAgfQogICAgbGZ0W3hdPWxmdFtub2RlXTsKICAgIHJodFt4XT1yaHRbbm9kZV07CiAgICBpbnQgbWlkPShzdGFydCtlbmQpLzI7CiAgICBpZihwb3M8PW1pZCkKICAgICAgICBsZnRbeF09dXBkYXRlKGxmdFt4XSxzdGFydCxtaWQscG9zLHZhbCk7CiAgICBlbHNlCiAgICAgICAgcmh0W3hdPXVwZGF0ZShyaHRbeF0sbWlkKzEsZW5kLHBvcyx2YWwpOwogCiAgICB0cmVlW3hdPXRyZWVbbGZ0W3hdXSt0cmVlW3JodFt4XV07CiAKICAgIHJldHVybiB4Owp9CiAKaW5saW5lIGludCBxdWVyeShpbnQgbm9kZSxpbnQgc3RhcnQsaW50IGVuZCxpbnQgbCxpbnQgcikKewogICAgaWYoc3RhcnQ+ciB8fCBlbmQ8bCkKICAgICAgICByZXR1cm4gMDsKICAgIGVsc2UgaWYoc3RhcnQ+PWwgJiYgZW5kPD1yKQogICAgICAgIHJldHVybiB0cmVlW25vZGVdOwogICAgaW50IG1pZD0oc3RhcnQrZW5kKS8yOwogICAgaW50IHExPXF1ZXJ5KGxmdFtub2RlXSxzdGFydCxtaWQsbCxyKTsKICAgIGludCBxMj1xdWVyeShyaHRbbm9kZV0sbWlkKzEsZW5kLGwscik7CiAKICAgIHJldHVybiAocTErcTIpOwp9CiAKIAppbnQgbWFpbigpCnsKICAgIHN0ZDppb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKICAgIGludCBuOwogICAgcyhuKTsKIAogICAgaW50IGk7CiAKICAgICAgaWR4PTA7CiAgICAgICByb290WzBdPTA7CiAgICAgICAgYnVpbGQoMCwxLG4pOwogCiAgICBpbnQgdD0xOwogICAgZm9yKGk9MTtpPD1uO2krKykKICAgIHsKICAgICAgICBzKGFyW2ldKTsKICAgICAgICBpbnQgaz1wb3NbYXJbaV1dOwogICAgICAgIGlmKGshPTApCiAgICAgICAgewogICAgICAgICAgICByb290W3RdPXVwZGF0ZShyb290W3QtMV0sMSxuLGssMCk7CiAgICAgICAgICAgIHQrKzsKICAgICAgICAgICAgcm9vdFt0XT11cGRhdGUocm9vdFt0LTFdLDEsbixpLDEpOwogICAgICAgICAgICB0Kys7CiAgICAgICAgfQogICAgICAgIGVsc2UKICAgICAgICB7CiAgICAgICAgICAgIHJvb3RbdF09dXBkYXRlKHJvb3RbdC0xXSwxLG4saSwxKTsKICAgICAgICAgICAgdCsrOwogICAgICAgIH0KIAogICAgICAgIHJ0W2ldPXQtMTsKICAgICAgICBwb3NbYXJbaV1dPWk7CiAgICB9CiAKICAgIGludCBtOwogICAgcyhtKTsKIAogICAgd2hpbGUobS0tKQogICAgewogICAgICAgIGludCBhLGI7CiAgICAgICAgcyhhKTsKICAgICAgICBzKGIpOwogCiAgICAgICAgcChxdWVyeShyb290W3J0W2JdXSwxLG4sYSxiKSk7CiAgICAgICAgZW50OwogICAgfQogCiByZXR1cm4gMDsKIAp9