#include<iostream>
#include<cmath>
#include<vector>
#include<climits>
#include<algorithm>
#include<numeric>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<set>
#include<random>
#include<cassert>
using namespace std;
#define ll long long int
#define ld long double

// MO's Algorithms


struct node{
	// for query
	ll l; // begin
	ll r; // end
	ll in ; // index
	};
ll cnt=0;

bool cmp(node A, node B)
{
if(A.l == B.l)
{
	return (A.r<B.r);
}
return (A.l<B.l);	
}

vector<ll> f(1000005,0);
ll beg=1, End=0;


int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);	

ll n;
cin>>n;
ll a[n+2];

for(ll i=1;i<=n;i++){cin>>a[i];}
ll q;
cin>>q;
node Q[q+1];
ll ans[n+3] ;
for(ll i=1;i<=q;i++)
{
	ll s ,e;
	cin>>s>>e;
	Q[i].l = s;
	Q[i].r=e;
	Q[i].in=i;
}
// sort:

sort(Q+1,Q+1+q,cmp);
for(ll i=1;i<=q;i++)
{
	ll st = Q[i].l;
	ll en = Q[i].r;
	
	// change freq as per req;
	while(beg<st)
	{
	// rem cur 
	 f[a[beg]]--;
	 if(f[a[beg]]==0){cnt--;}
	 beg++;
	}
	while(beg>st)
	{
	beg--;	
	f[a[beg]]++;
	if(f[a[beg]]==1){cnt++;}	
	}
	
	while(End<en)
	{
	End++;
	f[a[End]]++;
	if(f[a[End]]==1){cnt++;}	
	}
	
	while(End>en)
	{
	f[a[End]]--;
	if(f[a[End]]==0){cnt--;}
	End--;	
	}

	ans[Q[i].in] = cnt ;
}

for(ll i=1;i<=q;i++)
{
cout<<ans[i]<<endl;	
}

return 0;
}