#include<bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
#include "DEBUG.h"
#define bug(...) __f (#__VA_ARGS__, __VA_ARGS__)
#endif
#define first_in_out ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long int
#define double long double
#define min_heap priority_queue <ll, vector<ll>, greater<ll>>
#define print(a) for(auto x : a) cout << x << " ";
#define printpair(a) for(auto x : a) cout << x.first << " " << x.second<<"\n";
const ll N = 1e6 + 1;
int cnt[N];
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
struct query {
ll l, r, block, index, cnt;
bool operator<(query P) const
{
return make_pair(this->block, this->r) < make_pair(P.block, P.r);
}
};
void add(ll val)
{
cnt[val]++;
}
void remove(ll val)
{
cnt[val]--;
}
void solve()
{
ll n, queries;
cin >> n ;
cin >> queries;
ll a[n];
ll m = sqrt(n) + 1;
for (ll i = 0; i < n; i++)
cin >> a[i];
query q[queries];
for (ll i = 0; i < queries; i++)
{
cin >> q[i].l >> q[i].r;
q[i].l--, q[i].r--;
q[i].block = q[i].l / m;
q[i].index = i;
}
sort(q, q + queries);
ll i = 0, j = 0;
for (ll k = 0; k < queries; k++)
{
while (i < q[k].l)
{ remove(a[i]);
i++;
}
while (i > q[k].l )
{
i--;
add(a[i]);
}
while (j < q[k].r + 1)
{
add(a[j]);
j++;
}
while (j > q[k].r + 1)
{
j--;
remove(a[j]);
}
int res = 1e9;
for (int z = 0; z <= 100; z++)
{
int rdm = q[k].l + rng() % (q[k].r - q[k].l + 1);
if (cnt[rdm] > (q[k].r - q[k].l + 1) / 3)
{
res = min(res, rdm);
}
}
res = (res == 1e9) ? -1 : res;
q[k].cnt = res;
}
sort(q, q + queries, [](query & a, query & b) {
return a.index < b.index;
});
for (ll i = 0; i < queries; i++)
cout << q[i].cnt << "\n";
}
int main()
{
first_in_out
//clock_t z = clock();
ll t = 1;
while (t--)
solve();
//cerr << "Run Time : " << ((double)(clock() - z) / CLOCKS_PER_SEC);
}