#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")
const int N = 2e5+5;
vector<int> p[N];
int a[N];
void solve() {
int n,q;
cin >> n >> q;
for(int i = 1; i <= n; i++) {
cin >> a[i];
p[a[i]].push_back(i);
}
for(int i = 0; i < q; i++) {
int l, r;
cin >> l >> r;
int sz = r - l + 1, ans = INT_MAX;
srand(time(0));
for(int j = 0; j <= 50; j++) {
int idx = l + rand() % sz;
int v = a[idx];
int cnt = upper_bound(p[v].begin(),p[v].end(),r) - upper_bound(p[v].begin(),p[v].end(),l-1);
if(cnt > (r - l + 1) / 3) ans = min(ans, v);
}
if(ans == INT_MAX) cout << -1 << '\n';
else cout << ans << '\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;
}