#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <unordered_map>
std::unordered_map<int,int>mp[4011],s[4011],tmp;
int n,m,sid,eid,ans,y,a[100011],id[100011];
int fun(int l,int r)
{
	sid=id[l],eid=id[r];
	ans=0,y=0;tmp.clear();
	if(sid==eid)
	{
		for(register int j=l; j<=r; ++j)
		{
			++tmp[a[j]];
			if(tmp[a[j]]>y)y=tmp[a[j]],ans=a[j];
			if(tmp[a[j]]==y&&a[j]<ans)ans=a[j];
		}
		return ans;
	}
	for(register int j=l; id[j]==sid; ++j)++tmp[a[j]];
	for(register auto o:s[sid])tmp[o.first]-=o.second;
	for(register auto o:s[eid-1])tmp[o.first]+=o.second;
	for(register int j=r; id[j]==eid; --j)++tmp[a[j]];
	for(register auto o:tmp)
	{
		if(tmp[o.first]>y)y=tmp[o.first],ans=o.first;
		if(tmp[o.first]==y&&o.first<ans)ans=o.first;
	}
	return ans;
}
int main()
{
	 freopen("P4168_5.in","r",stdin);
	 freopen("P4168_5.out","w",stdout);
	scanf("%d %d",&n,&m);
	int o=(int)(sqrt(n)-1.2*log2(n)+1.358*log10(n));
	if(o>n)o=n;register int i,j;
	for(i=1; i<=n; ++i)id[i]=(i/o)+1;
	for(i=1; i<=n; ++i)
	{
		scanf("%d",a+i);
		mp[id[i]][a[i]]++;
	}int t=0;
	while(!mp[++t].empty())
	{
		for(register auto o:mp[t]) s[t][o.first]+=o.second;
		for(register auto o:s[t-1])s[t][o.first]+=o.second;
	}
	for(int i=1,x=0,y,l0,r0,l,r; i<=m; ++i)
	{
		scanf("%d %d",&l0,&r0);
		l=(l0+x-1)%n+1;
		r=(r0+x-1)%n+1;
		x=y=0;
		if(l>r)std::swap(l,r);
		printf("%d\n",x=fun(l,r));
	}
	return 0;
}

本人太懒，懒得写注释，大佬勿喷.

主要思路就是分块+前缀和