#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m,tal,cnt,kind[N],rt[N];
struct Tree{int rs,ls,val;}t[N*50];
struct Segment_Tree{
	void build(int &pos,int l,int r)
	{
		pos=++cnt;
		if(l==r) return ;
		int mid=(l+r)>>1;
		build(t[pos].ls,l,mid);
		build(t[pos].rs,mid+1,r);
	}
	void update(int &pos,int prev,int l,int r,int x)
	{
		pos=++cnt;
		t[pos].val=t[prev].val,t[pos].ls=t[prev].ls,t[pos].rs=t[prev].rs;
		if(l==r)
		{
			t[pos].val=1;
			return ;
		}
		int mid=(l+r)>>1;
		if(x<=mid) update(t[pos].ls,t[prev].ls,l,mid,x);
		else update(t[pos].rs,t[prev].rs,mid+1,r,x);
		t[pos].val=t[t[pos].ls].val+t[t[pos].rs].val;
	}
}T;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>kind[i];
		tal=max(tal,kind[i]);
	}
	T.build(rt[0],1,n);
	for(int i=1;i<=n;i++)
		T.update(rt[i],rt[i-1],1,n,kind[i]);
	cin>>m;
	while(m--)
	{
		int px,py;
		cin>>px>>py;
		cout<<t[rt[py]].val-t[rt[px-1]].val<<"\n";
	}
	return 0;
}