#include<bits/stdc++.h>
using namespace std;
const int N = 5e4 + 10;
const int M = 1010;
int turn[N],Q,n,a[N],b[N],len,s,tot,L[M],R[M],sum[M][N],q[M][M],cnt[N],pos[N];
void prework() {
	for(int j = 1; j <= tot; j ++)
		for(int i = L[j]; i <= R[j]; i ++)
			sum[j][a[i]] ++;
	for(int i = 1; i <= len; i ++)
		for(int j = 1; j <= tot; j ++)
			sum[j][i] += sum[j - 1][i];
	for(int i = 1; i <= tot; i ++) 
		for(int j = i ; j <= tot; j ++) {
			q[i][j] = q[i][j - 1];
			for(int k = L[j]; k <= R[j]; k ++) {
				if(sum[j][a[k]] - sum[i - 1][a[k]] > sum[j][q[i][j]] - sum[i - 1][q[i][j]]|| (sum[j][a[k]] - sum[i - 1][a[k]] == sum[j][q[i][j]] - sum[i - 1][q[i][j]] && a[k] < q[i][j]) ) q[i][j] = a[k];
			}
		}
}
int query(int l,int r) {
	if(pos[l] == pos[r] || pos[l] + 1 == pos[r]) {
		int ans = 0;
		int j = pos[l];
		for(int i = l;i <= r;i ++) cnt[a[i]] ++;
		for(int i = l ; i <= r; i ++) 
			if(cnt[a[i]]  > cnt[ans]  || (cnt[a[i]] == cnt[ans] && a[i] < ans) ) ans = a[i];
		for(int i = l; i <= r; i++) cnt[a[i]] = 0;
		return ans;
	}
	int block = pos[l],ans = q[pos[l] + 1][pos[r] - 1],x = l;
	while(l <= R[block]) {
		cnt[a[l]] ++;
		if(cnt[a[l]] + sum[pos[r] - 1][a[l]] - sum[pos[l]][a[l]] > cnt[ans] +  sum[pos[r] - 1][ans] - sum[pos[l]][ans] || (cnt[a[l]] + sum[pos[r] - 1][a[l]] - sum[pos[l]][a[l]] > cnt[ans] +  sum[pos[r] - 1][ans] - sum[pos[l]][ans] && ans > a[l])) ans = a[l];
		l ++;
	}
	l = L[pos[r]];
	while(l <= r) {
		cnt[a[l]] ++;
		if(cnt[a[l]] + sum[pos[r] - 1][a[l]] - sum[pos[l]][a[l]] > cnt[ans] +  sum[pos[r] - 1][ans] - sum[pos[l]][ans] || (cnt[a[l]] + sum[pos[r] - 1][a[l]] - sum[pos[l]][a[l]] > cnt[ans] +  sum[pos[r] - 1][ans] - sum[pos[l]][ans] && ans > a[l])) ans = a[l];
		l ++;
	}
	for(int i = x;i <= R[block];i ++) cnt[a[i]] = 0;
	for(int i = L[pos[r]];i <= r;i ++) cnt[a[i]] = 0;
	return ans ;
}
signed main() {
	ios ::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin >> n >> Q;
	s = sqrt(n);
	tot = (n + s - 1) / s;
	L[1] = 1;
	for(int i = 2; i <= tot; i ++) L[i] = min(L[i - 1] + s,n);
	R[tot] = n;
	for(int i = 1; i < tot; i ++) R[i] = L[i + 1] - 1;
	for(int i = 1; i <= n ; i++) cin >> a[i],b[i] = a[i];
	sort(b + 1,b + n + 1);
	len = unique(b + 1,b + n + 1) - b - 1;
	for(int i = 1; i <= n ; i ++) {
		pos[i] = ceil(1.0 * i / s);
		int x = a[i];
		a[i] = lower_bound(b + 1,b +len + 1,a[i]) - b;
		turn [a[i]] = x;
	}
	int l,r,lst = 0;
	while(Q--) {
		cin >> l >> r;
		l = (l + lst - 1) % n + 1,r = (r +lst - 1) % n + 1;
		if(l > r) swap(l,r);
		lst = turn[query(l,r)];
		cout << lst << '\n';
	}
	return 0;
}