/*
author : TIT_manh
*/
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <stack>
#include <deque>
#include <bitset>
#include <numeric>
#include <functional>
#include <cassert>
#include <sstream>
#include <climits>
#define ll long long
#define FOR(i,l,r) for (int i = l; i <= r; i++)
#define FOD(i,r,l) for (int i = r; i >= l; i--)
#define ALL(x) x.begin(), x.end()
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define fi first
#define se second
#define pb push_back
#define endl "\n"
#define m_int 0x3f3f3f3f
#define m_ll 0x3f3f3f3f3f3f3f3f
using namespace std;
const int maxn = 2e5 + 5;
int n, q, l[maxn], r[maxn], bit[maxn];
vector<int> pos[maxn];
vector<int> v[maxn];
vector<pair<int, int>> que;
void ciin() {
cin >> n >> q;
int x;
FOR(i,1,n) {
cin >> x;
pos[x].pb(i);
}
que.pb({0, 0});
int t1, t2;
FOR(i,1,q) {
cin >> t1 >> t2;
que.pb({t1, t2});
l[i] = 1; r[i] = (t2 - t1 + 1);
v[(l[i] + r[i]) >> 1].pb(i);
}
}
int ans[maxn];
void update(int i) {
while (i <= n) {
bit[i] += 1;
i += i & -i;
}
}
int sum(int i) {
int res = 0;
while (i > 0) {
res += bit[i];
i -= i & -i;
}
return res;
}
int get(int l, int r) {
return sum(r) - sum(l - 1);
}
void solve() {
int N = 2e5;
FOR(tt,1,18) {
FOR(i,1,n) bit[i] = 0;
FOD(mid,N,1) {
if ((int)pos[mid].size() > 0) for (auto& i : pos[mid]) update(i);
if ((int)v[mid].size() == 0) continue;
for (auto& i : v[mid]) {
if (get(que[i].fi, que[i].se) >= mid) {
l[i] = mid + 1;
ans[i] = mid;
if (l[i] > r[i]) continue;
int m = (l[i] + r[i]) >> 1;
v[m].pb(i);
}
else {
r[i] = mid - 1;
if (l[i] > r[i]) continue;
int m = (l[i] + r[i]) >> 1;
v[m].pb(i);
}
}
v[mid].clear();
}
}
FOR(i,1,q) cout << ans[i] << endl;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ciin(); solve();
return 0;
}
