#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+10;
const int mod=10007;
int a[N],b[N],pos[N],pl[N],pr[N],n,m,tt,t[N],num[N],tot,x;
int s[300][300],f[300][300];
int val(int x){
    return lower_bound(b+1,b+1+tot,x)-b;
}
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}
int voilent(int l,int r){
    for(int i=l;i<=r;i++) t[a[i]]++;
    int maxx=a[l];
    for(int i=l+1;i<=r;i++){
	if(t[a[i]]>t[maxx]||(t[a[i]]==t[maxx]&&maxx>a[i])) maxx=a[i];
    }
    for(int i=l;i<=r;i++) t[a[i]]=0;
    return b[maxx];
}
int query(int l,int r){
    int L=pos[l],R=pos[r];
    if(R-L<=1) return voilent(l,r);
    int maxx=f[L+1][R-1];
    for(int i=l;i<=pr[L];i++) t[a[i]]++;
    for(int i=pl[R];i<=r;i++) t[a[i]]++;
    for(int i=l;i<=pr[L];i++){
	int x=t[a[i]]+s[R-1][a[i]]-s[L][a[i]];
	int y=t[maxx]+s[R-1][maxx]-s[L][maxx];
	if(x>y) maxx=a[i];
	else if(x==y) maxx=min(maxx,a[i]);
    }
    for(int i=pl[R];i<=r;i++){
	int x=t[a[i]]+s[R-1][a[i]]-s[L][a[i]];
	int y=t[maxx]+s[R-1][maxx]-s[L][maxx];
	if(x>y) maxx=a[i];
	else if(x==y) maxx=min(maxx,a[i]);
    }
    for(int i=l;i<=pr[L];i++) t[a[i]]=0;
    for(int i=pl[R];i<=r;i++) t[a[i]]=0;
    return b[maxx];
}
void build(){
    for(int i=1;i<=pos[n];i++){
	pl[i]=pr[i-1]+1,pr[i]=min(n,pl[i]+tt-1);
	for(int j=pl[i];j<=pr[i];j++) s[i][a[j]]++;
	for(int j=1;j<=tot;j++) s[i][j]+=s[i-1][j];//维护前缀和
    }
    for(int i=1;i<=pos[n];i++){
	for(int j=i;j<=pos[n];j++){
	    int maxx=f[i][j-1];
	    for(int k=pl[j];k<=pr[j];k++){
		int x=s[j][a[k]]-s[i-1][a[k]],y=s[j][maxx]-s[i-1][maxx];
		if(x>y) maxx=a[k];
		else if(x==y) maxx=min(maxx,a[k]);
	    }
	    f[i][j]=maxx;
	}
    }
}
signed main(){
    n=read();m=read();
    tt=sqrt(n);
    for(int i=1;i<=n;i++){
	b[i]=a[i]=read();
	pos[i]=(i-1)/tt+1;
    }
    sort(b+1,b+1+n);
    tot=unique(b+1,b+1+n)-(b+1);//tot表示离散化后的个数
    for(int i=1;i<=n;i++) a[i]=val(a[i]);
    build();
    for(int i=1;i<=m;i++){
	int l=read(),r=read();
	l=(l+x-1)%n+1,r=(r+x-1)%n+1;
	if(l>r) swap(l,r);
	x=query(l,r);
	cout<<x<<endl;
    }
    return 0;
}