//#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 4e4 + 10, K = 310;
int n, m, now, cnt, len, lst;
int Tr[N], c[N], b[N], s[N][K];
bool vis[N];
inline ll read(){
	ll x = 0, m = 1;
	char ch = getchar();
	while(!isdigit(ch)){
		if(ch == '-') m = -1;
		ch = getchar();
	}
	while(isdigit(ch)){
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	return x * m;
}
inline void write(ll x){
	if(x < 0){
		putchar('-');
		write(-x);
		return;
	}
	if(x >= 10) write(x / 10);
	putchar(x % 10 + '0');
}
struct Code{
	int x, id;
}a[N], p[K][K];
inline bool cmp(Code x, Code y){
	return x.x < y.x;
}
inline void solve(){
	now = 1, cnt = (int) sqrt(n), len = (n + cnt - 1) / cnt;
	for(int i = 1; i <= n; ++ i){
		if(a[i].x != a[i - 1].x) b[a[i].id] = now, ++ now;
		else b[a[i].id] = now;
		Tr[now] = a[i].x;
	}
    for(int i = 1; i <= len; ++ i){
    	for(int j = 1; j <= n; ++ j) s[i][b[j]] = s[i - 1][b[j]];
    	for(int j = (i - 1) * cnt + 1; j <= min(n, i * cnt); ++ j) ++ s[i][b[j]];
	}
	for(int i = 1; i <= len; ++ i){
		memset(c, false, sizeof c);
		Code tmp; tmp.x = tmp.id = 0;
		for(int j = i; j <= len; ++ j){
			for(int k = (j - 1) * cnt + 1; k <= min(n, j * cnt); ++ k){
				++ c[b[k]];
				if(c[b[k]] > tmp.x){
					tmp.x = c[b[k]];
					tmp.id = b[k];
				}else if(c[b[k]] == tmp.x) tmp.id = min(tmp.id, b[k]);
			}
			p[i][j] = tmp;
		}
	}
}
inline int getid(int x){
	int sum = x / cnt + (x % cnt > 0);
	return sum;
}
inline int getans1(int l, int r, int L, int R){
	int ans = 0;
	for(int i = l; i <= r; ++ i) c[b[i]] = 0;
	for(int i = l; i <= r; ++ i){
		++ c[b[i]];
		if(c[b[i]] > c[ans]) ans = b[i];
		else if(c[b[i]] == c[ans]) ans = min(ans, b[i]);
	}
	write(lst = Tr[ans]), putchar('\n');
}
inline int getans2(int l, int r, int L, int R){
	int ans = p[L + 1][R - 1].id;
	c[ans] = vis[ans] = 0;
	for(int i = l; i <= min(n, L * cnt); ++ i) c[b[i]] = vis[b[i]] = 0;
	for(int i = (R - 1) * cnt + 1; i <= min(n, R * cnt); ++ i) c[b[i]] = vis[b[i]] = 0;
	for(int i = l; i <= min(n, L * cnt); ++ i) ++ c[b[i]];
	for(int i = (R - 1) * cnt + 1; i <= min(n, R * cnt); ++ i) ++ c[b[i]];
	int maxsum = 0, maxid = 0;
	for(int i = l; i <= min(l, L * cnt); ++ i){
		if(!vis[b[i]]){
			vis[b[i]] = 1;
			int val = c[b[i]] + s[R - 1][b[i]] - s[L][b[i]];
			if(maxsum < val) maxsum = val, maxid = b[i];
			else if(maxsum == val) maxid = min(maxid, b[i]);
		}
	}
	for(int i = (R - 1) * cnt + 1; i <= r; ++ i){
		if(!vis[b[i]]){
			vis[b[i]] = 1;
			int val = c[b[i]] + s[R - 1][b[i]] - s[L][b[i]];
			if(maxsum < val) maxsum = val, maxid = b[i];
			else maxid = min(maxid, b[i]);
		}
	}
	if(maxsum > c[ans] + p[L + 1][R - 1].x) ans = maxid;
	else if(maxsum == c[ans] + p[L + 1][R - 1].x) ans = min(ans, maxid);
	write(lst = Tr[ans]), putchar('\n');
}
signed main(){
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);
    n = read(), m = read();
    for(int i = 1; i <= n; ++ i) a[i].x = read(), a[i].id = i;
	sort(a + 1, a + 1 + n, cmp), solve();
	while(m --){
		int l = read(), r = read();
		l = (l + lst - 1) % n + 1, r = (r + lst - 1) % n + 1;
		if(l > r) swap(l, r);
		int L = getid(l), R = getid(r);
		R - L <= 2 ? getans1(l, r, L, R) : getans2(l, r, L, R);
	}
	return 0;
}