#define _GLIBCXX_FILESYSTEM
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
gp_hash_table<int, int, custom_hash> mp;
const int N = 2e5+2, B = 125;
int a[N];
set<pair<int,int>,greater<pair<int,int>>> st;
void remove(int idx) {
if(st.find({mp[a[idx]],a[idx]}) != st.end()) st.erase({mp[a[idx]],a[idx]});
mp[a[idx]]--;
if(mp[a[idx]]) st.insert({mp[a[idx]],a[idx]});
}
void add(int idx) {
if(st.find({mp[a[idx]],a[idx]}) != st.end()) st.erase({mp[a[idx]],a[idx]});
mp[a[idx]]++;
st.insert({mp[a[idx]],a[idx]});
}
int get_answer(int l) {
if(st.empty()) return -1;
auto it = st.begin();
int ans = INT_MAX;
if((*it).first > l) ans = min(ans, (*it).second);
st.erase(st.begin());
if(st.size()) {
auto it1 = st.begin();
if((*it1).first > l) ans = min(ans, (*it1).second);
}
st.insert({(*it).first,(*it).second});
if(ans == INT_MAX) return -1;
return ans;
}
struct Query {
int l, r, idx;
bool operator < (const Query &x) const {
if(l / B == x.l / B) return ((l / B) & 1) ? r > x.r : r < x.r;
return l / B < x.l / B;
}
};
vector<int> mo_s_algorithm(vector<Query> queries) {
vector<int> answers(queries.size());
sort(queries.begin(), queries.end());
int cur_l = 0;
int cur_r = -1;
for (Query q : queries) {
while (cur_l > q.l) {
cur_l--;
add(cur_l);
}
while (cur_r < q.r) {
cur_r++;
add(cur_r);
}
while (cur_l < q.l) {
remove(cur_l);
cur_l++;
}
while (cur_r > q.r) {
remove(cur_r);
cur_r--;
}
answers[q.idx] = get_answer((q.r - q.l + 1) / 3);
}
return answers;
}
void solve() {
int n,q;
cin >> n >> q;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
vector<Query> query(q);
for(int i = 0; i < q; i++) {
cin >> query[i].l >> query[i].r;
query[i].idx = i;
}
vector<int> ans = mo_s_algorithm(query);
for(int i = 0; i < q; i++)
cout << ans[i] << '\n';
return;
}
int32_t main() {
ios_base::sync_with_stdio(false);cin.tie(NULL);
int tc = 1;
// cin >> tc;
for(int kase = 1; kase <= tc; kase++) {
//cout << "Case " << kase << ": ";
solve();
}
return 0;
}