//Oh? You're Approaching Me?
#include <bits/stdc++.h>
using namespace std;
#define int long long
//
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef long double ld;
// #pragma GCC optimize("O3,unroll-loops")
#define migmig ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
#define X first
#define Y second
#define SZ(x) ll((x).size())
#define all(x) (x).begin(), (x).end()
#define cl clear
#define endl '\n'
#define deb(x) cerr << #x << " = " << x << '\n'
#define dokme(x) {cout << x << endl; return;}
#define wtf cout << "[ahaaaaaaaaaaaaaaaa]" << endl;
const int maxn = 2e5 + 21;
// const int mod = 1e9 + 7;
const int inf = 2e9;
const int LOG = 50;
const int sq = 500;
//g++ main.cpp -o main && main.exe
#define lc (id * 2)
#define rc (lc + 1)
#define mid ((l + r) / 2)
int n, q, ql[maxn], qr[maxn], p[maxn], L[maxn], R[maxn], fen[maxn];
vector<int> pbs[maxn], pos[maxn];
void add(int ps, int x) {
for (; ps <= n; ps += (ps & (-ps)))
fen[ps] += x;
}
int get(int ps) {
int ret = 0;
for (; ps > 0; ps -= (ps & (-ps)))
ret += fen[ps];
return ret;
}
int get(int l, int r) {
return get(r) - get(l - 1);
}
signed main() {
migmig;
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> p[i];
pos[p[i]].pb(i);
}
for (int i = 1; i <= q; i++) {
cin >> ql[i] >> qr[i];
L[i] = 1, R[i] = qr[i] - ql[i] + 2;
}
for (int i_ = 0; i_ < LOG; i_++) {
for (int i = 1; i <= n; i++)
pbs[i].clear();
for (int i = 1; i <= n; i++) {
if (R[i] - L[i] > 1)
pbs[(R[i] + L[i]) / 2].pb(i);
}
fill(fen, fen + maxn, 0);
for (int i = n; i >= 1; i--) {
for (int x : pos[i])
add(x, 1);
for (int x : pbs[i]) {
int ret = get(ql[x], qr[x]);
if (ret >= i)
L[x] = i;
else
R[x] = i;
}
}
}
for (int i = 1; i <= q; i++)
cout << L[i] << '\n';
}
