#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
using namespace std;
struct ff{int x,y,num;}f[55555]={},g[55555]={};
bool cmp1(ff m,ff n){return m.x<n.x;}int h[55555]={};
bool cmp2(ff m,ff n){return m.num<n.num;}int ans=0;//明显要先离散化
int l,r;int cnt[55555]={};int n,m;//分成两部分，只出现一次的部分和出现超过一次的部分，这样进行暴力明显快了不少，出现一次的那些数字可以用线段树
bool vis1[55555]={},vis2[55555]={};//vis1==只出现一次的那些数字,vis2==只出现一次的数字所在的位置
int gug=1;int tree[272222]={};int top;//数字最大为top，下标最大为n
int next1[55555]={},next2[55555]={};
int findd(int a,int b,int c,int d,int e)
{
	if(a==c&&b==d)
		return tree[e];
	int zhong=c+d>>1;
	if(b<=zhong)
		return findd(a,b,c,zhong,e*2);
	if(a>zhong)
		return findd(a,b,zhong+1,d,e*2+1);
	return min(findd(a,zhong,c,zhong,e*2),findd(zhong+1,b,zhong+1,d,e*2+1));
}
void lisanhua()
{
	sort(f+1,f+n+1,cmp1);
	f[1].y=1;
	for(int i=2;i<=n;i++)
		if(f[i].x==f[i-1].x)
			f[i].y=f[i-1].y;
		else
			f[i].y=f[i-1].y+1;
	for(int i=1;i<=n;i++)
		h[f[i].y]=f[i].x;
	top=f[n].y;
	sort(f+1,f+1+n,cmp2);
}
void codeforces()
{
	for(int i=1;i<=n;i++)
		cnt[f[i].y]++;
	for(int i=1;i<=n;i++)
		if(cnt[f[i].y]==1)
			vis2[i]=1,vis1[f[i].y]=1;
	next1[top]=top+1,next2[n]=n+1;
	for(int i=top-1;i>=0;i--)
		if(vis1[i+1])
			next1[i]=next1[i+1];
		else
			next1[i]=i+1;
	for(int i=n-1;i>=0;i--)
		if(vis2[i+1])
			next2[i]=next2[i+1];
		else
			next2[i]=i+1;
	for(int i=1;i<=n;i++)
		if(cnt[f[i].y]==1)
			tree[i+gug-1]=f[i].y;
	for(int i=gug-1;i>0;i--)
		tree[i]=min(tree[i*2],tree[i*2+1]);
	for(int i=1;i<=n;i++)
		cnt[i]=0;
	return;
}
void slove(int s,int t)
{
	for(int i=next1[0];i<=top;i=next1[i])
		cnt[i]=0;
	for(int i=next2[s-1];i<=t;i=next2[i])
		cnt[f[i].y]++;
	int maxx=0;int weizhi=2147483647;
	for(int i=next1[0];i<=top;i=next1[i])
		if(maxx<cnt[i])
			maxx=cnt[i],weizhi=i;
	if(maxx<=1)
		weizhi=min(weizhi,findd(s,t,1,gug,1));
	ans=h[weizhi];
}
int main()
{
	freopen("numquery.in","r",stdin);
	freopen("numquery.out","w",stdout);
	scanf("%d%d",&n,&m);
	while(gug<n)gug<<=1;
	for(int i=1;i<=gug*2;i++)
		tree[i]=2147483647;
	for(int i=1;i<=n;i++)
		scanf("%d",&f[i].x),f[i].num=i;
	lisanhua();
	for(int i=1;i<=m;i++)
		scanf("%d%d",&g[i].x,&g[i].y);
	codeforces();
	for(int i=1;i<=m;i++)
	{
		l=(g[i].x+ans-1)%n+1;
		r=(g[i].y+ans-1)%n+1;
		if(l>r)swap(l,r);
		slove(l,r);
		printf("%d\n",ans);
	}
	return 0;
}