#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[114514],val[114514],before[114514];
int size,belong[114514],bl[114514],br[114514],bnum;
int sum[1145][40005];//Ç°i¸ö¿éÿ¸öÊýµÄ³öÏÖ´ÎÊý
int maxnum[1145][1145];//µÚi-j¸ö¿éµÄÖÚÊý 
int cnt[114514];
int tot;
void init()
{
	for(int i=1;i<=n;i++)
		val[i]=a[i];
	sort(val+1,val+n+1);
	tot=unique(val+1,val+n+1)-val-1;
	for(int i=1;i<=n;i++)
	{
		int k=lower_bound(val+1,val+tot+1,a[i])-val;
		a[i]=k;
		before[a[i]]=val[k];
	}
//	for(int i=1;i<=n;i++)
//		cout<<a[i]<<" "<<before[a[i]]<<endl;
}
void bld()
{
	size=sqrt(n);
	bnum=ceil(1.0*n/size);
	for(int i=1;i<=bnum;i++)
	{
		bl[i]=(i-1)*size+1;
		br[i]=i*size;
		for(int j=bl[i];j<=br[i];j++)
			belong[j]=i;
	}
	br[bnum]=n;
	for(int i=1;i<=bnum;i++)
	{
		for(int j=bl[i];j<=br[i];j++)
			++sum[i][a[j]];
		for(int j=1;j<=tot;j++)
			sum[i][j]+=sum[i-1][j];
	}
	for(int i=1;i<=bnum;i++)
		for(int j=i;j<=bnum;j++)
		{
			int maxn=maxnum[i][j-1];
			for(int k=bl[j];k<=br[j];k++)
				if(sum[j][maxn]-sum[i-1][maxn]<sum[j][a[k]]-sum[i-1][a[k]]||
				sum[j][maxn]-sum[i-1][maxn]==sum[j][a[k]]-sum[i-1][a[k]]&&maxn>a[k])
					maxn=a[k];
			maxnum[i][j]=maxn;
		}
//	for(int i=1;i<=bnum;i++)
//		for(int j=i;j<=bnum;j++)
//			cout<<i<<" "<<j<<" "<<maxnum[i][j]<<endl;
}
int bsum(int l,int r,int x)
{
	return sum[belong[r]][x]-sum[belong[l]-1][x];
}
int query(int l,int r)
{
	memset(cnt,0,sizeof cnt);
	if(belong[l]==belong[r])
	{
		int res=0,maxn=0;
		for(int i=l;i<=r;i++)
		{
			++cnt[a[i]];
			if(maxn<cnt[a[i]]||maxn==cnt[a[i]]&&a[i]<res)
				maxn=cnt[a[i]],res=a[i];
		}
		return before[res];
	}
	int bmax=maxnum[belong[l]][belong[r]];
	int maxn=bsum(l,r,bmax),res=bmax;
	for(int i=l;i<=br[belong[l]];i++)
	{
		++cnt[a[i]];
		if(cnt[a[i]]+bsum(l,r,a[i])>maxn)
			res=a[i],maxn=cnt[a[i]]+bsum(l,r,a[i]);
		if(cnt[a[i]]+bsum(l,r,a[i])==maxn&&a[i]<res)
			res=a[i];
	}
	for(int i=bl[belong[r]];i<=r;i++)
	{
//		cout<<a[i]<<" "<<cnt[a[i]]<<endl;
		++cnt[a[i]];
		if(cnt[a[i]]+bsum(l,r,a[i])>maxn)
			res=a[i],maxn=cnt[a[i]]+bsum(l,r,a[i]);
		if(cnt[a[i]]+bsum(l,r,a[i])==maxn&&a[i]<res)
			res=a[i];
	}
	if(maxn<bsum(l,r,bmax))
		res=bmax;
	if(maxn==bsum(l,r,bmax)&&bmax<res)
		res=bmax;
	return before[res];
}
int ans;
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	init();
	bld();
	while(m--)
	{
		int l,r;
		cin>>l>>r;
		l=(l+ans-1)%n+1,r=(r+ans-1)%n+1;
		if(l>r)
			swap(l,r);
//		cout<<l<<" "<<r<<endl;
		ans=query(l,r);
		cout<<ans<<endl;
	}
}