#include <iostream>
using namespace std;
const int p=3e7,q=1e6;
template <class type>
class segment_tree
{
	private:
		template <class node_type>
		struct node
		{
			int l,r;
			int ls,rs;
			node_type sum;
		};
		node<type> t[p+5];
		int cur,root[q+5];
		inline int mid(int l,int r)
		{
			return (l+r)/2;
		}
		inline void create(int id)
		{
			if(t[id].l!=t[id].r&&t[id].ls==0&&t[id].rs==0)
			{
				cur++;
				t[id].ls=cur;
				t[t[id].ls].l=t[id].l;
				t[t[id].ls].r=mid(t[id].l,t[id].r);
				cur++;
				t[id].rs=cur;
				t[t[id].rs].l=mid(t[id].l,t[id].r)+1;
				t[t[id].rs].r=t[id].r;
			}
		}
		void print(int id)
		{
			cout<<id<<"号节点: l:"<<t[id].l<<" r:"<<t[id].r<<" ls:"<<t[id].ls<<" rs:"<<t[id].rs<<" sum:"<<t[id].sum<<"\n";
		}
		void change_(int hid,int id,int x,type delta)
		{
			t[id].sum+=delta; 
			if(t[id].l==t[id].r&&t[id].l==x)
				return ;
			create(hid);
			if(x<=mid(t[id].l,t[id].r))
			{
				t[id].rs=t[hid].rs;
				cur++;
				t[id].ls=cur;
				t[cur].l=t[id].l;
				t[cur].r=mid(t[id].l,t[id].r);
				t[cur].sum=t[t[hid].ls].sum;
				change_(t[hid].ls,t[id].ls,x,delta);
			}
			else
			{
				t[id].ls=t[hid].ls;
				cur++;
				t[id].rs=cur;
				t[cur].l=mid(t[id].l,t[id].r)+1;
				t[cur].r=t[id].r;
				t[cur].sum=t[t[hid].rs].sum;
				change_(t[hid].rs,t[id].rs,x,delta);
			}
		}
		type request_(int id,int l,int r)
		{
			if(t[id].l==l&&t[id].r==r)
				return t[id].sum;
			create(id);
			int mid_=mid(t[id].l,t[id].r);
			bool f1=l<=mid_,f2=mid_+1<=r;
			if(f1&&!f2)
				return request_(t[id].ls,l,r);
			else if(!f1&&f2)
				return request_(t[id].rs,l,r);
			else if(f1&&f2)
				return request_(t[id].ls,l,mid_)+request_(t[id].rs,mid_+1,r);
		}
	public:
		void build(int n)
		{
			cur++;
			root[0]=cur;
			t[cur].l=0;
			t[cur].r=n;
		}
		void change(int hid,int id,int x,type delta)
		{
			cur++;
			t[cur].l=0;
			t[cur].r=t[root[0]].r;
			t[cur].sum=t[root[hid]].sum;
			root[id]=cur;
			change_(root[hid],root[id],x,delta);
		}
		type request(int id,int l,int r)
		{
			return request_(root[id],l,r);
		}
};
segment_tree<int> t;
int n,m;
int a[1000005],last[1000005];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n;
	t.build(n);
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		t.change(i-1,i,last[a[i]],1);
		last[a[i]]=i;
	}
	cin>>m;
	for(int i=1;i<=m;i++)
	{
		int l,r;
		cin>>l>>r;
		cout<<t.request(r,0,l-1)-t.request(l-1,0,l-1)<<"\n";
	}
	cout<<endl;
	return 0;
}

评测记录