#include<bits/stdc++.h>
using namespace std;
int n,a[50010],m,b[100010],pos[50010],k;
struct node{
int l,r,id,ans;
}q[200010];
int cmp(node a,node b)
{
return (pos[a.l] == pos[b.l] ? a.r < b.r : a.l < b.l);
}
int cmp1(node a,node b)
{
return a.id < b.id;
}
int main()
{
cin>>n;
for(int i=1; i<=n; i++)
cin>>a[i];
cin>>m; k=(int)sqrt(n);
for(int i=1; i<=m; i++)
cin>>q[i].l>>q[i].r,q[i].id=i,pos[i]=
(int)(i-1)/k+1;
sort(q+1, q+m+1,cmp);
int l=1,r=0,ans=0;
for(int i=1; i<=m; i++)
{
while(r < q[i].r) { b[a[r+1]]++; r++; if(b[a[r]] == 1) ans++;}
while(r > q[i].r) { b[a[r]]--; r--; if(b[a[r+1]] == 0) ans--;}
while(l < q[i].l) { b[a[l]]--; l++; if(b[a[l-1]] == 0) ans--;}
while(l > q[i].l) { b[a[l-1]]++; l--; if(b[a[l]] == 1) ans++;}
q[i].ans=ans;
}
sort(q+1,q+m+1,cmp1);
for(int i=1; i<=m; i++) cout<<q[i].ans<<endl;
return 0;
}
by Eagle_WYX @ 2018-02-21 22:13:10
ok
by Eagle_WYX @ 2018-02-22 08:17:29