#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);
}