#include<bits/stdc++.h>
using namespace std;
int rt,st,ed,ll,rr,x,y,n,m,t,k,S,s,tt,ans1,ans2,ans,zong[1001][1001],a[4000001],b[4000001],l[4000001],r[4000001],sum[4000001],f[1001][1001],pr[4000001];
bool ff[10000001];
inline int js(int x,int y)
{
	if(y-x<2*S)
	{
		ans2=0x7fffffff/3,ans1=-0x7fffffff/3;
		for(int i=x; i<=y; ++i)
			if(!ff[a[i]]) ff[a[i]]=true,sum[a[i]]=1;
			else ++sum[a[i]];
		for(int i=x; i<=y; ++i)
			if(ff[a[i]])
			{
				if((sum[a[i]]>ans1)||(sum[a[i]]==ans1&&a[i]<ans2)) ans1=sum[a[i]],ans2=a[i];
				ff[a[i]]=false;
			}
	}
	else
	{
		ll=x/S+1,rr=y/S+1;
		if(x==l[ll]) --ll;
		if(y==r[rr]) ++rr;
		ans2=zong[ll+1][rr-1],ans1=f[ans2][rr-1]-f[ans2][ll],ed=r[ll],st=l[rr];
		for(int i=x; i<=ed; ++i)
			if(!ff[a[i]]) ff[a[i]]=true,sum[a[i]]=1;
			else ++sum[a[i]];
		for(int i=st; i<=y; ++i)
			if(!ff[a[i]]) ff[a[i]]=true,sum[a[i]]=1;
			else ++sum[a[i]];
		for(int i=x; i<=ed; ++i)
			if(ff[a[i]])
			{
				int lcq=f[a[i]][rr-1]-f[a[i]][ll]+sum[a[i]];
				if((lcq>ans1)||(lcq==ans1&&a[i]<ans2)) ans1=lcq,ans2=a[i];
				ff[a[i]]=false;
			}
		for(int i=st; i<=y; ++i)
			if(ff[a[i]])
			{
				int lcq=f[a[i]][rr-1]-f[a[i]][ll]+sum[a[i]];
				if((lcq>ans1)||(lcq==ans1&&a[i]<ans2)) ans1=lcq,ans2=a[i];
				ff[a[i]]=false;
			}
	}
	return b[ans2];
}
int main()
{
	scanf("%d%d",&n,&m),S=sqrt(n);
	for(int i=0; i<n; ++i) scanf("%d",&a[i]),b[i]=a[i];
	sort(b,b+n),t=unique(b,b+n)-b;
	for(int i=0; i<n; ++i) a[i]=lower_bound(b,b+t,a[i])-b;
	for(int i=0; i<n; ++i) if(i%S==0) r[tt]=i-1,l[++tt]=i;
	r[tt]=n-1,l[tt+1]=r[tt+1]=n;
	for(int i=1; i<=tt; ++i)
	{
		for(int j=l[i]; j<n; ++j) sum[a[j]]=0;
		k=l[i],ans1=-0x7fffffff/3,ans2=0x7fffffff/3;
		for(int j=i; j<=tt; ++j)
		{
			for(; k<=r[j]; ++k)
			{
				++sum[a[k]],rt=sum[a[k]];
				if((rt>ans1)||(rt==ans1&&a[k]<ans2))  ans1=rt,ans2=a[k];
			}
			zong[i][j]=ans2;
		}
	}
	memset(sum,0,sizeof(sum));
	for(int i=1; i<=tt; ++i)
	{
		for(int j=0; j<t; ++j) f[j][i]=f[j][i-1];
		for(int j=l[i]; j<=r[i]; ++j) f[a[j]][i]=++sum[a[j]];
	}
	while(m--)
	{
		scanf("%d%d",&x,&y),x=(x+ans-1)%n,y=(y+ans-1)%n;
		if(x>y) swap(x,y);
		ans=js(x,y),printf("%d\n",ans);
	}
	return 0;
}