求调

#include<bits/stdc++.h>
using namespace std;
const int maxn = 40000 + 10;
int n,m,dot = 0,_n,zu;
int b[maxn],cnt[maxn],s[1000][40000 + 10],p[1000][1000],tong[40000 + 10];
struct node {
	int x,id,pos;
}a[maxn];
bool compare (node a,node b) {
	return a.x < b.x;
}
bool cmp(node a,node b) {
	return a.pos < b.pos;
}
void build() {
	for (int i = 1; i <= zu; i++) {
		for (int j = (i - 1) * _n + 1; j <= (min(n,i * _n)); j++) {
			s[i][a[j].id]++;
		}
		for (int j = 1; j <= dot; j++) {
			s[i][j] += s[i - 1][j];
		} 
	}
	for (int i = 1; i <= zu; i++) {
		for (int j = i; j <= zu; j++) {
			int shu = p[i][j - 1];
			for (int k = (j - 1) * _n + 1; k <= min(n,j * _n); k++) {
				if(((s[j][a[k].id] - s[i - 1][a[k].id]) > (s[j][shu] - s[i - 1][shu]))|| ((s[j][a[k].id] - s[i - 1][a[k].id] == s[j][shu] - s[i - 1][shu]) && a[k].id < shu)) {
					shu = a[k].id;
				}
			}
			p[i][j] = shu;
		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
    _n = (int)sqrt(n),zu = (n - 1) / _n + 1;
	for (int i = 1; i <= n; i++) {
		cin >> b[i];
		a[i].x = b[i];
		a[i].pos = i;
	}
	sort(a + 1,a + n + 1,compare);
	for (int i = 1; i <= n; i++) {
		if(i == 1) {
			a[i].id = ++dot;
		}
		else {
			if(a[i].x > a[i - 1].x) {
				a[i].id = ++dot;
			}
			else {
				a[i].id = dot;
			}
		}
    }
    sort(a + 1, a + n + 1,cmp);
//	for (int i = 1; i <= n; i++) {
//		cout << a[i].x << " " <<a[i].id << " " << a[i].pos << "\n";
//	}
	int last = 0;
	build();
	memset(tong,0,sizeof(tong));
	for (int i = 1; i <= m; i++) {
		int l,r,l0,r0,ans = -1,now;
		cin >> l0 >> r0;
		l = ((l0 + last - 1) % n) + 1;
		r = ((r0 + last - 1) % n) + 1;
//		cout << l << " " << r << " lr\n";
		if (l > r) swap(l,r);
		int blkl = (l - 1) / _n + 1,blkr = (r - 1) / _n + 1;
		if(blkr - blkl <= 1) {
			int mx = -1,now;
			for (int j = l; j <= r; j++) {
				tong[a[j].id]++;
				if((tong[a[j].id] > mx) || (tong[a[j].id] == mx && a[j].x <= now)) {
					mx = tong[a[j].id];
					now = a[j].x;
				}
			}
			last = now;
			for (int j = l; j <= r; j++) {
				tong[j] = 0;
			} 
		}
		else {
			int now = p[blkl + 1][blkr - 1];
			for (int j = l; j <= _n * blkl; j++) {
				tong[a[j].id]++;
			}
			for (int j = _n * (blkr - 1) + 1; j <= r; j++) {
				tong[a[j].id]++;
			}
			for (int j = l; j <= _n * blkl; j++) {
				int x1 = tong[a[j].id] + s[blkr - 1][a[j].id] - s[blkl][a[j].id];
				int x2 =  tong[now] + s[blkr - 1][now] - s[blkl][now];
				if(x1 > x2||(x1 == x2 && a[j].id < now)) {
					now = a[j].id;
					last = a[j].x;
				}
			}
			for (int j = _n * (blkr - 1) + 1; j <= r; j++) {
				int x1 = tong[a[j].id] + s[blkr - 1][a[j].id] - s[blkl][a[j].id];
				int x2 =  tong[now] + s[blkr - 1][now] - s[blkl][now];
				if (x1 > x2 || (x1 == x2 && a[j].id < now)) {
					now = a[j].id;
					last = a[j].x;
				}
			}
			for (int j = l; j <= _n * blkl; j++) {
				tong[a[j].id] = 0;
			}
			for (int j = _n * (blkr - 1) + 1; j <= r; j++) {
				tong[a[j].id] = 0;
			}
		} 
//		for (int i = 1; i <= dot; i++) {
//			cout << cnt[i] << " cnt\n";
//		}
		cout << last << "\n";
	}
	return 0;
}