#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
#include <cmath>
using namespace std;
struct Query {
int l, r, idx;
};
bool cmp(const Query& a, const Query& b) {
int block_size = 1000;
if (a.l / block_size != b.l / block_size) {
return a.l < b.l;
}
return a.r < b.r;
}
vector<int> moAlgorithm(int n, int q, const vector<int>& a, const vector<Query>& queries) {
vector<int> res(q);
vector<int> freq(n + 1, 0);
int currentL = 0, currentR = 0;
for (int i = 0; i < q; ++i) {
int l = queries[i].l - 1;
int r = queries[i].r - 1;
while (currentR <= r) {
freq[a[currentR]]++;
currentR++;
}
while (currentR > r + 1) {
currentR--;
freq[a[currentR]]--;
}
while (currentL < l) {
freq[a[currentL]]--;
currentL++;
}
while (currentL > l) {
currentL--;
freq[a[currentL]]++;
}
int threshold = (r - l + 1) / 3;
int minX = numeric_limits<int>::max();
for (int j = 1; j <= n; ++j) {
if (freq[j] > threshold) {
minX = min(minX, j);
}
}
res[queries[i].idx] = (minX == numeric_limits<int>::max()) ? -1 : minX;
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
vector<Query> queries(q);
for (int i = 0; i < q; ++i) {
cin >> queries[i].l >> queries[i].r;
queries[i].idx = i;
}
sort(queries.begin(), queries.end(), cmp);
vector<int> res = moAlgorithm(n, q, a, queries);
for (int r : res) {
cout << r << endl;
}
return 0;
}