#include<bits/stdc++.h>
using namespace std;
#define re register
inline void read(int &res){
	res=0;
	int f=1;
	char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9')res=(res<<1)+(res<<3)+c-48,c=getchar();
	res*=f;
}
int n,m;
int l,r;
int tot;
int flag[500005];
map<int,int>vis;
int fk[500005];
int cs[500005];
int f[800][800];
int s[800][800];
int bak[500005];
int fr[500005];
int num[500005];
int pos[500005];
int mx;
int ks;
int cnt[600015];
vector<int>v[500005];
bool isf[500005],isb[500005];
int las;
int sqr;
signed main()
{
    freopen("ynoi.in", "r", stdin);
	read(n);read(m);
    sqr=sqrt(n);
    for(re int i=1;i<=n;i++){
    	fk[i]=i/sqr+1;
    	if(fk[i]>fk[i-1]){//块的分界线 
    		bak[ks++]=i-1;//上一块的末位置 
    		fr[ks]=i;//该块开头位置 
    		isb[i-1]=isf[i]=1;//标记是否为起点和终点 
		}
	}
	bak[ks]=n;
	isb[n]=1;
    for(re int i=1;i<=n;i++){
    	read(cs[i]);
    	if(!vis[cs[i]]){
    		vis[cs[i]]=++tot;//数值的标记 
    		num[tot]=cs[i];//该类对应数值 
		}
		flag[i]=vis[cs[i]];//属于哪一类 
		v[flag[i]].push_back(i);
		pos[i]=v[flag[i]].size()-1;//该类型中其位置 
	}
	for(re int i=1;i<=ks;i++){
		int k=fr[i]-1;
		mx=0;
		memset(cnt,0,sizeof(cnt));
		for(re int j=i;j<=ks;j++){//第i块到第j块一共的情况 
			s[i][j]=s[i][j-1];
			while(k<bak[j]){
				++k;
				cnt[flag[k]]++;
				if(cnt[flag[k]]>mx||(cnt[flag[k]]==mx&&cs[k]<num[s[i][j]])){
					mx=cnt[flag[k]];
					s[i][j]=flag[k];//众数是哪一类 
				}
			}
			f[i][j]=mx;//众数的个数 
		}
	}
	while(m--){
		read(l);read(r);
		l=(l+las-1)%n+1,r=(r+las-1)%n+1;
		if(l>r)swap(l,r);
		int ll=fk[l]+(isf[l]?0:1),rr=fk[r]-(isb[r]?0:1);
		//cout<<ll<<" "<<rr<<endl;
		if(ll>rr){//在同一块内 
			mx=0;
			memset(cnt,0,4*(tot+20));
			for(int i=l;i<=r;i++){
				cnt[flag[i]]++;
				if(cnt[flag[i]]>mx||cnt[flag[i]]==mx&&cs[i]<num[las]){
					mx=cnt[flag[i]];
					las=flag[i];
				}
			}
		}
		else {//不同块，区间内部有完整块 
			mx=f[ll][rr];
			las=s[ll][rr];
			//cout<<mx<<" "<<las<<endl;
			int kl=fr[ll],kr=bak[rr];
			while(kl>l){
				int s=flag[--kl];
				if(pos[kl]+mx>=v[s].size())continue;
				if(v[s][pos[kl]+mx]<=kr||v[s][pos[kl]+mx-1]<=kr&&cs[kl]<num[las]){//往后找mx个仍在范围内 
					mx++;
					las=s;
				}
			}
			while(kr<r){
				int s=flag[++kr];
				if(pos[kl]<mx)continue;
				if(v[s][pos[kl]-mx]>=kl||v[s][pos[kl]-mx+1]>=kl&&cs[kr]<num[las]){//往前找mx个仍在范围内 
					mx++;
					las=s;
				}
			}
		}
		printf("%d\n",las=num[las]);
	}
	return 0;
}