#include<algorithm>

#include<cstdio>

#include<queue>

#define I (J+1)

#define J (i+j>>1)

#define P (k<<1)

#define S (P^1)

using namespace std;

const int N=1e5+5;

int n,m;

typedef int arr[N];

arr p,q,f,a;

struct heap{

	priority_queue<int>s,t;

	void ins(int j){

		s.push(j);

	}

	void del(int j){

		t.push(j);

	}

	int top(){

		while(t.size()&&s.top()==t.top())

			s.pop(),t.pop();

		return s.size()?s.top():0;

	}

}c[1<<18];

typedef struct node*ptr;

struct node{

	ptr i,j;

	int s;

}e[N*136];

ptr z=e+1,r[N];

int eval(int v,ptr s,int i=1,int j=n){

	if(i==j)

		return s->s;

	return max(s->s,v<I?eval(v,s->i,i,J):eval(v,s->j,I,j));

}

struct info{

	void(heap::*foo)(int);

	int f,s,t;

};

void vary(info f,ptr&s,int i=1,int j=n,int k=1){

	s=&(*z++=*s);

	if(f.s<=i&&j<=f.t){

		(c[k].*f.foo)(f.f);

		s->s=c[k].top();

	}

	else{

		if(f.s<I)

			vary(f,s->i,i,J,P);

		if(f.t>J)

			vary(f,s->j,I,j,S);

	}

}

struct edge{

	edge*s;

	info f;

}e2[N*2];

edge*z2=e2,*y[N];

int main(){

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;++i){

		scanf("%d",a+i);

		p[i]=f[a[i]],f[a[i]]=i;

	}

	fill(f+1,f+n+1,n+1);

	for(int i=n;i;--i)

		q[i]=f[a[i]],f[a[i]]=i;

	for(int i=n;i;--i){

		int s=p[i]+1,t=i+1;

		edge u={

			y[s],&heap::ins,a[i],i,q[i]-1

		};

		edge v={

			y[t],&heap::del,a[i],i,q[i]-1

		};

		*(y[s]=z2++)=u;

		*(y[t]=z2++)=v;

	}

	*(*r=e)=(node){

		e,e

	};

	for(int i=1;i<=n;++i){

		r[i]=r[i-1];

		for(edge*j=y[i];j;j=j->s)

			vary(j->f,r[i]);

	}

	int k=0,s,t;

	while(m--){

		scanf("%d%d",&s,&t);

		if((s=(s+k)%n+1)>(t=(t+k)%n+1))

			swap(s,t);

		printf("%d\n",k=eval(t,r[s]));

	}

}