#include<bits/stdc++.h>
using namespace std;

const int M = 4e4 + 5, N = sqrt(4e4 + 5);
int n, m, B, tot, cnt, a[M], b[M], f[N][N], f_k[N][N], t[N];	
vector <int> G[M];
struct bucket{
	int mx, mxid, t[M];
	void insert(int x) {
		++t[x];
		if(t[x] > mx) mx = t[x], mxid = x;
		else if(t[x] == mx) mxid = min(mxid, x);
	}
}buc;

int get_block(int x) { return (x + B - 1) / B; }
int sub1(int x) { return B * (x - 1) + 1; }
int sub2(int x) { return min(B * x, n); }

inline void pre_G() {
	sort(b + 1, b + n + 1);
	int sum = unique(b + 1, b + n + 1) - b - 1;
	for(int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + sum + 1, a[i]) - b;
	for(int i = 1; i <= n; i++) G[i].push_back(0);
	for(int i = 1; i <= n; i++) G[a[i]].push_back(i);
	return;
}

int count(int x, int l, int r) {
	return upper_bound(G[x].begin(), G[x].end(), r) - upper_bound(G[x].begin(), G[x].end(), l - 1);
}

inline void pre_mode() {
	cnt = get_block(n);
	for(int i = 1; i <= cnt; i++) {
		int p = sub1(i) - 1;
		for(int j = i; j <= cnt; j++) {
			while(p < sub2(j)) buc.insert(a[++p]);
			f[i][j] = buc.mxid, f_k[i][j] = buc.mx;
		}
		memset(buc.t, 0, sizeof(buc.t));
		buc.mx = buc.mxid = 0;
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	B = sqrt(n);
	for(int i = 1; i <= n; i++) cin >> a[i], b[i] = a[i];
	pre_G(), pre_mode();
	int l, r;
	while(m--) {
		cin >> l >> r;
		int lb = get_block(l), rb = get_block(r);
		if((l - 1) % B) lb++;
		if(r % B) rb--;
		int ans_v = f[lb][rb], ans_k = f_k[lb][rb];
		for(int i = l, e = sub1(lb); i < e; i++) {
			int tmp = count(a[i], l, r);
			if(tmp >= ans_k) ans_k = tmp, ans_v = min(ans_v, a[i]);
		}
		for(int i = sub2(rb) + 1; i <= r; i++) {
			int tmp = count(a[i], l, r);
			if(tmp >= ans_k)  ans_k = tmp, ans_v = min(ans_v, a[i]);
		}
		cout << b[ans_v] << "\n";
	}
	return 0;
}