#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using namespace std;
using ll = long long;
const int MX = 300005;
const int B = 800;
int a[MX], freq[MX];
map<int,int> nums[MX], block[MX];
int n, n_blocks;
struct Query {
int i, l, r, block;
Query() {}
Query(int i, int l, int r) : i(i), l(l), r(r) {
block = l/B;
}
bool operator < (const Query& other) {
if (block == other.block) return ((block & 1) ? (r < other.r) : (r > other.r));
return (block < other.block);
}
};
int block_get(int ind) {
if (ind >= n) return n_blocks;
return ind/B;
}
int block_get_start(int block) {
return (B*block);
}
int block_get_end(int block) {
return min(n-1, B*(block+1)-1);
}
void include(int i) {
int& x = a[i];
int b1, b2;
b1 = block_get(freq[x]);
nums[freq[x]][x] -= 1;
if (nums[freq[x]][x] == 0) nums[freq[x]].erase(x);
freq[x] += 1;
b2 = block_get(freq[x]);
nums[freq[x]][x] += 1;
if (b1 != b2) {
block[b1][x] -= 1;
if (block[b1][x] == 0) block[b1].erase(x);
block[b2][x] += 1;
}
}
void exclude(int i) {
int& x = a[i];
int b1, b2;
b1 = block_get(freq[x]);
nums[freq[x]][x] -= 1;
if (nums[freq[x]][x] == 0) nums[freq[x]].erase(x);
freq[x] -= 1;
b2 = block_get(freq[x]);
nums[freq[x]][x] += 1;
if (b1 != b2) {
block[b1][x] -= 1;
if (block[b1][x] == 0) block[b1].erase(x);
block[b2][x] += 1;
}
}
int query(int l) {
int i, b, ret;
b = block_get(l);
ret = INT_MAX;
for (i = block_get_end(b); i >= l; --i) {
if (!nums[i].empty()) ret = min(ret, nums[i].begin()->first);
}
for (i = b+1; i < n_blocks; ++i) {
if (!block[i].empty()) ret = min(ret, block[i].begin()->first);
}
if (ret == INT_MAX) ret = -1;
return ret;
}
int main() {
FAST;
memset(freq, 0, sizeof(freq));
int m, i, l, r, ql, qr, qi, len;
cin >> n >> m;
n_blocks = (n+B-1)/B;
for (i = 0; i < n; ++i) cin >> a[i];
for (i = 0; i < n; ++i) {
nums[0][a[i]] += 1;
block[0][a[i]] += 1;
}
vector<Query> q(m);
vector<int> ans(m);
for (i = 0; i < m; ++i) {
cin >> l >> r;
--l; --r;
q[i] = Query(i, l, r);
}
sort(q.begin(), q.end());
l = 0; r = -1;
for (i = 0; i < m; ++i) {
qi = q[i].i;
ql = q[i].l;
qr = q[i].r;
while (l > ql) include(--l);
while (r < qr) include(++r);
while (l < ql) exclude(l++);
while (r > qr) exclude(r--);
len = (qr - ql + 1) / 3;
ans[qi] = query(len+1);
}
for (i = 0; i < m; ++i) {
cout << ans[i] << "\n";
}
return 0;
}