#include<bits/stdc++.h>
#include<cmath>
using namespace std;
int n,m,a[40010],s[210][40010],f[210][210],j[210],cnt[40010],le,b[40010],l,r,g[40010],ans,h,q;
vector<int>e;
int main(){
	scanf("%d%d",&n,&m),q=m,le=sqrt(n);
	for(int w=1;w<=n;w++)scanf("%d",&a[w]),e.push_back(a[w]),g[w]=(w-1)/le+1;
	sort(e.begin(),e.end()),e.erase(unique(e.begin(),e.end()),e.end());
	for(int w=1,x;w<=n;w++)x=a[w],a[w]=(lower_bound(e.begin(),e.end(),a[w])-e.begin())+1,h=max(h,a[w]),b[a[w]]=x;
	for(int w=1;w<=g[n];w++){
		memcpy(s[w],s[w-1],sizeof(s[w-1]));
		for(int x=(w-1)*le+1;w==g[x];x++)s[w][a[x]]++;
	}
	for(int w=1,m=0;w<=g[n];w++,m=0)for(int x=w;x<=g[n];x++){
		for(int y=(x-1)*le+1;g[y]==x;y++)if(s[x][a[y]]-s[w-1][a[y]]>s[x][m]-s[w-1][m]||s[x][a[y]]-s[w-1][a[y]]==s[x][m]-s[w-1][m]&&a[y]<m)m=a[y];
		f[w][x]=m;
	}
	while(m--){
		scanf("%d%d",&l,&r),l=(l+b[ans]-1)%n+1,r=(r+b[ans]-1)%n+1,ans=0;
        for(int w=1;w<=h;w++)cnt[w]=j[w]=0;
		if(l>r)swap(l,r);
		int ll=g[l]+1,rr=g[r]-1;
		if(ll>rr){
			for(int w=l;w<=r;w++)if(++cnt[a[w]]>cnt[ans]||cnt[a[w]]==cnt[ans]&&a[w]<ans)ans=a[w];
			printf("%d\n",b[ans]);
		}else{
			ans=f[ll][rr],cnt[ans]=s[rr][ans]-s[ll-1][ans];
			for(int w=l;g[w]==g[l];w++){
				if(++cnt[a[w]]>cnt[ans]||cnt[a[w]]==cnt[ans]&&a[w]<ans)ans=a[w];
				if(!j[a[w]]){
					j[a[w]]=1;
                    if(a[w]!=f[ll][rr])cnt[a[w]]+=s[rr][a[w]]-s[ll-1][a[w]];
					if(cnt[a[w]]>cnt[ans]||cnt[a[w]]==cnt[ans]&&a[w]<ans)ans=a[w];
				}
			}
			for(int w=rr*le+1;w<=r;w++){
				if(++cnt[a[w]]>cnt[ans]||cnt[a[w]]==cnt[ans]&&a[w]<ans)ans=a[w];
				if(!j[a[w]]){
                    j[a[w]]=1;
                    if(a[w]!=f[ll][rr])cnt[a[w]]+=s[rr][a[w]]-s[ll-1][a[w]];
					if(cnt[a[w]]>cnt[ans]||cnt[a[w]]==cnt[ans]&&a[w]<ans)ans=a[w];
				}
			}
			printf("%d\n",b[ans]);
		}
	}
	return 0;
}

思路：分块，离散化后求出前 $i$ 块每个数出现次数，以及第 $l$ 到第 $r$ 块的众数（最小的），询问时只有众数或不满一块零散的数可能是答案。