[分块] 蒲公英

%%%%%%%%%%%%%%%%% TNT %%%%%%%%%%%%%%%

# include <iostream>
# include <cstdio>
# include <algorithm>
# include <cmath>
# define MAXN 40005

using namespace std;

int rd(){
	int x = 0; char ch = getchar();
	while(ch < '0' || ch > '9') ch = getchar();
	while(ch >='0' && ch <='9'){
		x = x * 10 + ch - '0';
		ch = getchar();
	}    
	return x;
}

// Partition Section

int a[MAXN], blk[MAXN], sizB;
int tmpLWB[MAXN]; // 离散化的辅助数组
int sum[250][MAXN]; // 处理每块中的颜色前缀和
int mod[250][250]; // mod[i][j] 从 i 块到 j 块的最小下标的众数
int cntCol[MAXN]; // 用于询问记录的桶

void Init(int n){
	
	// 离散化
	sort(tmpLWB+1, tmpLWB+n+1);
	int tmpL = unique(tmpLWB+1, tmpLWB+n+1) - tmpLWB - 1;

	for(int i = 1; i <= n; i++){
		a[i] = lower_bound(tmpLWB+1, tmpLWB+1+tmpL, a[i]) - tmpLWB;
	}

	// 前缀和处理
	int cntB = (n - 1) / sizB + 1; // 块的个数

	for(int i = 1; i <= n; i++){
		sum[blk[i]][a[i]] += 1;
	}
	for(int i = 1; i <= cntB; i++){
		for(int j = 1; j <= tmpL; j++){
			sum[i][j] += sum[i-1][j];
		}
	}

	// 众数处理
	for(int i = 1; i <= cntB; i++){
		for(int j = i; j <= cntB; j++){
			int maxM = mod[i][j-1];
			for(int k = (j-1)*sizB+1; k <= min(j*sizB, n); k++){
				if(maxM != k){
					if((sum[j][maxM]-sum[i-1][maxM]) < (sum[j][a[k]]-sum[i-1][a[k]]) || (((sum[j][maxM]-sum[i-1][maxM]) == (sum[j][a[k]]-sum[i-1][a[k]]))&&(a[k] < maxM))){
						maxM = a[k];
					}
				}
			}
			mod[i][j] = maxM;
		}
	}

} // 预处理离散化 + 前缀和 + 众数

int Query(int l, int r){
	int ans = 0;
	
	if(blk[r] - blk[l] <= 1){
		for(int i = l; i <= r; i++){
			cntCol[a[i]] += 1;
		}
		for(int i = l; i <= r; i++){
			if(cntCol[a[i]] > cntCol[ans] || (cntCol[a[i]] == cntCol[ans] && a[i] < ans)){
				ans = a[i];
			}
		}
		for(int i = l; i <= r; i++){
			cntCol[a[i]] = 0;
		}
		return ans;
	} // 相邻块

	for(int i = l; i <= sizB*blk[l]; i++){
		cntCol[a[i]] += 1;
	}	
	for(int i = sizB*(blk[r]-1)+1; i <= r; i++){
		cntCol[a[i]] += 1;
	}
	
	ans = mod[blk[l]+1][blk[r]-1];
	for(int i = l; i <= sizB*blk[l]; i++){
		int last = sum[blk[r]-1][ans] - sum[blk[l]][ans] + cntCol[ans];
		int now  = sum[blk[r]-1][a[i]]- sum[blk[l]][a[i]]+ cntCol[a[i]];
		if(last < now || (last == now && ans > a[i])){
			ans = a[i];
		}
	}
	for(int i = sizB*(blk[r]-1)+1; i <= r; i++){
		int last = sum[blk[r]-1][ans] - sum[blk[l]][ans] + cntCol[ans];
		int now  = sum[blk[r]-1][a[i]]- sum[blk[l]][a[i]]+ cntCol[a[i]];
		if(last < now || (last == now && ans > a[i])){
			ans = a[i];
		}
	}

	for(int i = l; i <= sizB*blk[l]; i++){
		cntCol[a[i]] = 0;
	}	
	for(int i = sizB*(blk[r]-1)+1; i <= r; i++){
		cntCol[a[i]] = 0;
	}

	return ans;
}

// Main Function

int main(){
	int n, m;
	n = rd(), m = rd();
	sizB = sqrt(n);
	for(int i = 1; i <= n; i++){
		tmpLWB[i] = a[i] = rd();
		blk[i] = (i-1) / sizB + 1;		
	}

	Init(n);
	
	long long ans = 0; int l = 0, r = 0;
	for(int i = 1; i <= m; i++){
		l = rd(), r = rd();
		l = (l+ans-1)%n + 1, r = (r+ans-1)%n + 1;
		if(l > r) swap(l, r); // 处理答案

		ans = Query(l, r);
		ans = tmpLWB[ans]; // 防止错解的处理

		printf("%d
", ans);  
	}

	return 0;
}