#include<bits/stdc++.h>
using namespace std;
const int N=5e4+5;
int a[N],sum[500][N],m[500][500],cnt[N];
int pos[N],b[N],L[N],R[N];
int n,mm;
int len;
void init()
{
	int t=sqrt(n);
	for(int i=1;i<=t;i++)
	{
		L[i]=R[i-1]+1;
		R[i]=i*t;
	}
	if(R[t]<n)
	{
		t++;
		R[t]=n;
		L[t]=R[t-1]+1;
	}
	for(int i=1;i<=t;i++)
	{
		for(int j=L[i];j<=R[i];j++)
		{
			pos[j]=i;
		}
	}
	for(int i=1;i<=t;i++)
	{
		for(int j=1;j<=len;j++) sum[i][a[j]]=sum[i-1][a[j]];
		for(int j=L[i];j<=R[i];j++)
		{
			sum[i][a[j]]++;
		}
	}
	for(int i=1;i<=t;i++)
	{
		int res=0,ans=0;
		for(int j=L[i];j<=n;j++)
		{			
			cnt[a[j]]++;
			if(cnt[a[j]]>res||(cnt[a[j]]==res&&a[j]<ans))
			{
				res=cnt[a[j]];
				ans=a[j];
			}
			m[i][pos[j]]=ans;
		}
		memset(cnt,0,sizeof cnt);
	}	
}
int enquir(int l,int r)
{
	int t=sqrt(n);
	int p=pos[l],q=pos[r];
	int ans=m[p+1][q-1],res=max(0,sum[q-1][ans]-sum[p][ans]);
	int lim=min(p*t,r),f=0;
	if(p!=q) f=1;
	for(int i=l;i<=lim;i++) cnt[a[i]]=max(0,sum[q-1][a[i]]-sum[p][a[i]]);
	if(f)
	{
		for(int i=L[q];i<=r;i++)
		{
			cnt[a[i]]=max(0,sum[q-1][a[i]]-sum[p][a[i]]);
		}
	}
	for(int i=l;i<=lim;i++)
	{
		cnt[a[i]]++;
		if(cnt[a[i]]>res||(cnt[a[i]]==res&&a[i]<ans))
		{
			ans=a[i];
			res=cnt[a[i]];
		}
	}
	if(f)
	{
		for(int i=L[q];i<=r;i++)
		{
			cnt[a[i]]++;
			if(cnt[a[i]]>res||(cnt[a[i]]==res&&a[i]<ans))
			{
				ans=a[i];
				res=cnt[a[i]];
			}
		}
	}
	return ans;
}
signed main()
{
	cin>>n>>mm;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		b[i]=a[i];
	}
	sort(b+1,b+1+n);
	len=unique(b+1,b+1+n)-b-1;
	for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+len,a[i])-b;
	init();
	int l,r,x=0;
	for(int i=1;i<=mm;i++)
	{
		cin>>l>>r;
		l=(l+x-1)%n+1,r=(r+x-1)%n+1;
		if(l>r) swap(l,r);
		x=b[enquir(l,r)];
		cout<<x<<endl;
	}
	return 0;
}