#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=40010;
int s[210][N],f[210][210];
int a[N],b[N];
int lef[N],righ[N];
int n,m,kkk,sc;
int q[N],t[N];
int dis(int x){
	return lower_bound(b+1,b+1+sc,x)-b;
}
void init(){
	int cnt=n/kkk;
	if(n%kkk)cnt++;
	for(int i=1;i<=cnt;i++){
		lef[i]=(i-1)*kkk+1;
		righ[i]=i*kkk;
	}
	righ[cnt]=n;
	for(int i=1;i<=cnt;i++){
		for(int j=lef[i];j<=righ[i];j++){
			s[i][a[j]]++;
			q[j]=i;
		}
		for(int j=1;j<=kkk;j++)s[i][j]+=s[i-1][j];
	}
	for(int i=1;i<=cnt;i++){
		for(int j=i;j<=cnt;j++){
			int res=f[i][j-1];
			for(int k=lef[j];k<=righ[j];k++){
				int v1=s[j][res]-s[i-1][res];
				int v2=s[j][a[k]]-s[i-1][a[k]];
				if(v1<v2)res=a[k];
				else if(v1==v2)res=min(res,a[k]);
			}
			f[i][j]=res;
		}
	}
}
int fb(int l,int r,int L,int R,int res){
    for(int i=l;i<=r;i++) {
        int v1=t[a[i]]+s[q[R]-1][a[i]]-s[q[L]][a[i]];
        int v2=t[res]+s[q[R]-1][res]-s[q[L]][res];
        if(v1>v2)res=a[i];
        else if(v1==v2)res=min(res,a[i]);
    }
    return res;
}
int query(int l,int r){
	if(q[r]-q[l]<=1){
		for(int i=l;i<=r;i++)t[a[i]]++;
		int res=a[l];
		for(int i=l+1;i<=r;i++){
			if(t[a[i]]>t[res])res=a[i];
			else if(t[a[i]]==t[res])res=min(res,a[i]);
		}
		for(int i=l;i<=r;i++)t[a[i]]=0;
		return b[res];
	}
	for(int i=l;i<=righ[q[l]];i++)t[a[i]]++;
    for(int i=lef[q[r]];i<=r;i++)t[a[i]]++;
    int ans=f[q[l]+1][q[r]-1];
    ans=fb(l,righ[q[l]],l,r,ans);
    ans=fb(lef[q[r]],r,l,r,ans);
    for(int i=l;i<=righ[q[l]];i++)t[a[i]]=0;
    for(int i=lef[q[r]];i<=r;i++)t[a[i]]=0;
    return b[ans];
}
signed main(){
	cin>>n>>m;
	kkk=sqrt(n);
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[i]=a[i];
	}
	sort(b+1,b+1+n);
	sc=unique(b+1,b+1+n)-b-1;
	for(int i=1;i<=n;i++)a[i]=dis(a[i]);
	init();
	int x=0;
	while(m--){
		int l0,r0;
		cin>>l0>>r0;
		int l=(l0+x-1)%n+1,r=(r0+x-1)%n+1;
		if(l>r)swap(l,r);
		x=query(l,r);
		cout<<x<<endl;
	}
	return 0;
}