/*                ___
   _______________| |_
  /\     pls don't    \
 /  \   downvote me    \
/____\__________________\
|    |                  |
|    | Date : 23/07/2025|
|    | Author : pppssslc|
|____|__________________|
*/
#include<bits/stdc++.h>

using namespace std;

typedef string str;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> vll;
typedef map<int, int> mpii;
typedef map<ll, ll> mpll;
typedef set<int> si;
typedef set<ll> sl;
#define prio_que priority_queue

#define se second
#define fi first
#define For(i, l, r, x) for(int i = l; i <= r; i += x)
#define Ford(i, l, r, x) for(int i = l; i >= r; i -= x)
#define Fore(x, a) for(auto x: a)
#define pb push_back
#define ins insert
#define all(a) a.begin(), a.end()

const ll inf = 1e18 + 1;
const int mod = 1e9 + 7;
const int maxn = 2e5 + 1;

vi val[maxn];
int bit[maxn], l[maxn], r[maxn], u[maxn], v[maxn], res[maxn];
int n, q;

void upd(int p){
	For(i, p, n, i&-i) ++bit[i];
}

int get(int p){
	int ret = 0;
	if(p == 0) return 0;
	Ford(i, p, 1, i&-i) ret += bit[i];
	return ret;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> n >> q;
	memset(res, -1, sizeof(res));
	For(i, 1, n, 1){
		int a; cin >> a;
		val[a].pb(i);
	}
	For(i, 1, q, 1){
		cin >> u[i] >> v[i];
		l[i] = 1, r[i] = n;
	}
	while(true){
		memset(bit, 0, sizeof(bit));
		bool check = true;
		vi qrs[n + 1];
		For(i, 1, q, 1){
			if(l[i] <= r[i]) check = false;
			else continue;
			qrs[(l[i] + r[i]) / 2].pb(i);
		}
		if(check) break;
		Ford(i, n, 1, 1){
			Fore(id, val[i])upd(id);
			Fore(id, qrs[i]){
				if(get(v[id]) - get(u[id] - 1) >= i){
					l[id] = i + 1;
					res[id] = i;
				}else r[id] = i - 1;
			}
		}
	}
	For(i, 1, q, 1) cout << res[i] << '\n';
	return (0 ^ 0);
}