#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define N 100010

using namespace std;

int v[N],lst[N],dic[N],nxt[N],d,l,r,ans,rt;

char *p1,*p2,buf[100000];

#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)

int rd() {int x=0,f=1; char c=nc(); while(c<48) {if(c=='-') f=-1; c=nc();} while(c>47) x=(((x<<2)+x)<<1)+(c^48),c=nc(); return x*f;}

inline void Max(int &x,int y) {x=x>y?x:y;}

inline void Min(int &x,int y) {x=x<y?x:y;}

struct Node {int p[3],mx[3],mn[3],ans,size,val,ls,rs;}a[N];

inline bool cmp(const Node &a,const Node &b)

{

	for(int i=0;i<3;i++) if(a.p[(d+i)%3]!=b.p[(d+i)%3]) return a.p[(d+i)%3]<b.p[(d+i)%3];

	return true;

}

inline void pushup(int x,int k)

{

	a[x].size+=a[k].size;

	for(int i=0;i<3;i++) Max(a[x].mx[i],a[k].mx[i]),Min(a[x].mn[i],a[k].mn[i]);

	Max(a[x].ans,a[k].ans);

}

int build(int l,int r,int now)

{

	int mid=(l+r)>>1;

	d=now; nth_element(a+l,a+mid,a+r+1,cmp);

	for(int i=0;i<3;i++) a[mid].mx[i]=a[mid].mn[i]=a[mid].p[i];

	a[mid].ans=a[mid].val;

	if(l<mid) a[mid].ls=build(l,mid-1,(now+1)%3),pushup(mid,a[mid].ls);

	if(mid<r) a[mid].rs=build(mid+1,r,(now+1)%3),pushup(mid,a[mid].rs);

	return mid;

}

bool judge(int x)

{

	return a[x].ans>ans&&a[x].mx[0]>=l&&a[x].mn[0]<=r&&a[x].mn[1]<l&&a[x].mx[2]>r;

}

void query(int x)

{

	if(!x||!judge(x)) return;

	if(a[x].p[0]>=l&&a[x].p[0]<=r&&a[x].p[1]<l&&a[x].p[2]>r) Max(ans,a[x].val);

	query(a[x].ls); query(a[x].rs);

}

int main()

{

	int n=rd(),m=rd();

	for(int i=1;i<=n;i++) v[i]=rd(),lst[i]=dic[v[i]],nxt[dic[v[i]]]=i,dic[v[i]]=i;

	for(int i=1;i<=n;i++) a[i].p[0]=i,a[i].p[1]=lst[i],a[i].p[2]=nxt[i]?nxt[i]:n+1,a[i].val=v[i];

	rt=build(1,n,0); while(m--)

	{

		l=(rd()+ans)%n+1,r=(rd()+ans)%n+1; if(l>r) swap(l,r);

		ans=0,query(rt); printf("%d\n",ans);

	}

	return 0;

}