#include<cstdio>
#include<map>
#include<math.h>
int n,m,a[40005],x,y,cnt=0,zs[205][205],uv[40005],fk[205][40005],jx,l,r,uc[40005];
std::map<int,int>lmap;
std::map<int,int>v;
int main(){
//	freopen("P4168_1.in","r",stdin);
//	freopen("out.txt","w",stdout);
	scanf("%d%d",&n,&m);
	x=sqrt(n)+1;
	for(int i=1;i<=n;i++){
		int _;
		scanf("%d",&_);
		if(!lmap[_])lmap[_]=++cnt,v[cnt]=_;
		a[i]=lmap[_];
	}
	for(int i=1;i<=x;i++){
		for(int j=1;j<=cnt;j++)uv[j]=0;
		int zzs=0,zss=-1;
		for(int j=i;j<=x;j++){
			for(int k=j*x-x+1;k<=j*x;k++){
				uv[a[k]]++;
				if(uv[a[k]]>zss)zss=uv[a[k]],zzs=a[k];
			}
			zs[i][j]=zzs; 
		}
	}
	for(int i=1;i<=x;i++){
		for(int j=1;j<=cnt;j++)fk[i][j]=fk[i-1][j];
		for(int j=i*x-x+1;j<=i*x;j++){
			fk[i][a[j]]++;
		}
	}
	while(m--){
		scanf("%d%d",&l,&r);
		l=((l+jx-1)%n)+1,r=((r+jx-1)%n)+1;
		if(l>r){
			int yh=l;
			l=r;
			r=yh;
		}
//		printf("%d->%d",l,r);
		if(r-l+1<=4*x){
			int ans[2];
			ans[1]=0;
			for(int i=l;i<=r;i++){
				uc[a[i]]++;
			}
			for(int i=l;i<=r;i++){
				if(uc[a[i]]>ans[1]||(uc[a[i]]==ans[1]&&v[a[i]]<v[ans[0]]))ans[1]=uc[a[i]],ans[0]=a[i]/*,printf("%d:%d	",a[i],uc[a[i]])*/;
				uc[a[i]]--;
			}
			jx=v[ans[0]];
		}
		else{
			int lx=(l+(x-1)*2)/x,rx=(r)/x;
			for(int i=l;i<=x*lx-x;i++){
				uc[a[i]]++;
			}
			for(int i=rx*x+1;i<=r;i++){
				uc[a[i]]++;
			}
			int ans[2];
			ans[0]=fk[rx][zs[lx][rx]]-fk[lx-1][zs[lx][rx]];
			ans[1]=zs[lx][rx];
			for(int i=l;i<=x*lx-x;i++){
				int zyh=uc[a[i]]+fk[rx][a[i]]-fk[lx-1][a[i]];
				if(zyh>ans[0]||(zyh==ans[0]&&v[a[i]]<v[ans[1]]))ans[0]=zyh,ans[1]=a[i];
				uc[a[i]]--;
			}
			for(int i=rx*x+1;i<=r;i++){
				int zyh=uc[a[i]]+fk[rx][a[i]]-fk[lx-1][a[i]];
				if(zyh>ans[0]||(zyh==ans[0]&&v[a[i]]<v[ans[1]]))ans[0]=zyh,ans[1]=a[i];
				uc[a[i]]--;
			}
			jx=v[ans[1]];
		}
		printf("%d\n",jx);
	}
}