本地AC提交WA

#include<bits/stdc++.h>
#define ll long long
#define SIZE 40005
using namespace std;
int n, m;
int a[SIZE];
int a_[SIZE];
int c[SIZE], top_c;
int c_[SIZE], top_c_;
int l[5005], r[5005], tong[SIZE];
int t;
int pos[SIZE];
vector<int>times[SIZE];
int maxnum[5005][5005], maxtimes[5005][5005]; 
void uniq(){
	for(int i = 1; i <= n; i++){
		if(c[i] == c[i + 1])continue;
		else c_[++top_c_] = c[i];
	}
}
void pre(){
	for(int i = 1; i <= n; i++){
		scanf("%d",&a[i]);
		c[++top_c] = a[i];
	}
	sort(c + 1, c + n + 1);
	uniq();
	for(int i = 1; i <= n; i++){
		int x = lower_bound(c_ + 1, c_ + top_c_ + 1, a[i]) - c_;
		a_[i] = x;
		times[x].push_back(i);
	}
	
	int T = sqrt(top_c_*log2(top_c_)); t = n / T;
	for(int i = 1; i <= t; i++){
		l[i] = (i - 1) * T + 1;
		r[i] = i * T;
	}
	if(r[t] < n)l[++t] = r[t - 1] + 1, r[t] = n; 
	for(int i = 1; i <= t; i++)
		for(int j = l[i]; j <= r[i]; j++)
			pos[j] = i;
}
int find1(int x, int y){
	int l = 0, r = times[y].size() - 1, mid = 0, res = 0;
	while(l <= r){
		mid = (l + r) >> 1;
		if(times[y][mid] <= x)res = mid, l = mid + 1;
		else r = mid - 1;
	}
	return res;
}
int find2(int x, int y){
	int l = 0, r = times[y].size() - 1, mid = 0, res = 0;
	while(l <= r){
		mid = (l + r) >> 1;
		if(times[y][mid] >= x)res = mid, r = mid - 1;
		else l = mid + 1;
	}
	return res;
}
void pre_make(){
	int maxx1 = 0, maxx2 = 0, maxx3 = 0;
	for(int i = 1; i <= t; i++){
		maxx1 = maxx2 = maxx3 = 0;
		for(int j = i; j <= t; j++){
			for(int k = l[j]; k <= r[j]; k++){
				tong[a_[k]]++;
				if(tong[a_[k]] > maxx1){
					maxx1 = tong[a_[k]], maxx2 = a[k], maxx3 = a_[k];
				}else if(tong[a_[k]] == maxx1){
					if(a[k] < maxx2) maxx2 = a[k], maxx3 = a_[k];
				}
			}
			maxnum[i][j] = maxx2; maxtimes[i][j] = tong[maxx3];
		}
		memset(tong, 0, sizeof(tong));
	}
}
int main(){
//	freopen("4168.in","r",stdin);
//	freopen("4168.out","w",stdout);
	scanf("%d%d",&n, &m);
	pre();
	pre_make();
	int last = 0, anss = 0;
	while(m--){
		int L = 0, R = 0;
		scanf("%d%d",&L, &R);
		L = (L + anss - 1) % n + 1, R = (R + anss - 1) % n + 1;
		last = 0, anss = 0;
		if(L > R) swap(L, R);

		if(pos[R] - pos[L] <= 1){
			for(int i = L; i <= R; i++){
				int x = a_[i];
				int p1 = find2(L, x); int p2 = find1(R, x);
				if(p2 - p1 + 1 > last){
					last = p2 - p1 + 1;anss = a[i];
				}else if(p2 - p1 + 1 == last){
					if(a[i] < anss) anss = a[i];
				}
			}
		} else {
			for(int i = L; i <= r[pos[L]]; i++){
				int x = a_[i];
				int p1 = find2(L, x); int p2 = find1(R, x);
				if(p2 - p1 + 1 > last){
					last = p2 - p1 + 1;anss = a[i];
				}else if(p2 - p1 + 1 == last){
					if(a[i] < anss) anss = a[i];
				}
			}
			for(int i = l[pos[R]]; i <= R; i++){
				int x = a_[i];
				int p1 = find2(L, x); int p2 = find1(R, x);
				if(p2 - p1 + 1 > last){
					last = p2 - p1 + 1;anss = a[i];
				}else if(p2 - p1 + 1 == last){
					if(a[i] < anss) anss = a[i];
				}
			}
			if(maxtimes[pos[L] + 1][pos[R] - 1] > last){
				last = maxtimes[pos[L] + 1][pos[R] - 1];
				anss = maxnum[pos[L] + 1][pos[R] - 1];
			} else if(maxtimes[pos[L] + 1][pos[R] - 1] == last){
				if(anss > maxnum[pos[L] + 1][pos[R] - 1]) anss = maxnum[pos[L] + 1][pos[R] - 1];
			}
		}
		printf("%d\n",anss);
	}
	return 0;
}