这可能是当前卡的最快的主席树了

#include<iostream>
#define I int  
#define F(a,b,c) for(register int a=b;a<=c;++a) 
const int LEN=1<<21;
char BUF[LEN],*Pin,*Pin_last,PUF[LEN],*Pout=PUF,*Pout_last=PUF+LEN-1;
inline char G(){return Pin==Pin_last&&(Pin_last=(Pin=BUF)+fread(BUF,1,LEN,stdin),Pin==Pin_last)?EOF:*Pin++;}
inline void P(char x){if(Pout==Pout_last)fwrite(PUF,1,Pout-PUF,stdout),Pout=PUF;*Pout++=x;}
inline int R(){int res=0,ch=' ';for(;(ch<'0'||ch>'9')&&ch!=EOF;ch=G());for(;ch>='0'&&ch<='9';ch=G())res=(res<<3)+(res<<1)+ch-48;return res;}
inline void wt(int a){if(a>9)wt(a/10);P(a%10+'0');return;}
inline void write(int a,char b){wt(a),P(b);}
/*头文件copy来的*/

const int N = 2e6+10;
I n,m,c,pre[N],pre2[N],l,r;

const int L = 20;
I trcnt,T[N];
struct TREE{
	I ls,rs,num;
}t[N*L];
#define ls(x) t[x].ls
#define rs(x) t[x].rs
inline I Mdfy(I pr,I a,I b,I s,I add){I x=++trcnt,mid=a+b>>1;
	t[x].num=t[pr].num+add;
	if(!(a^b)) return x;
	if(s<=mid) ls(x)=Mdfy(ls(pr),a,mid,s,add),rs(x)=rs(pr);
	else rs(x)=Mdfy(rs(pr),mid+1,b,s,add),ls(x)=ls(pr);
	return x;
}

signed main(){n=R(),c=R(),m=R();
	I lst,x,i,lim=n+1;
	for(i=1;i^lim;++i){x=R();
		if(pre[x]){lst;
			if(pre2[x]) lst=Mdfy(T[i-1],1,n,pre2[x],-1);
			else lst=T[i-1];
			T[i]=Mdfy(lst,1,n,pre[x],1);
		}
		else T[i]=T[i-1];
		pre2[x]=pre[x],pre[x]=i;
	}lim=m+1;
	for(i=1;i^lim;++i){l=R(),x=T[R()];
		I res=0,mid,a=1,b=n;
		while(a^b){
			if(l<=(mid=a+b>>1)) res+=t[rs(x)].num,x=ls(x),b=mid;
			else x=rs(x),a=mid+1;
		}
		write(res+t[x].num,'\n');
	}
	fwrite(PUF,1,Pout-PUF,stdout);
	return 0;
}