#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define all(x) (x).begin(),(x).end()
#define X first
#define Y second
#define sep ' '
#define endl '\n'
#define debug(x) cerr << #x << ": " << x << endl;
ll poww(ll a, ll b, ll md) {
return (!b ? 1 : (b & 1 ? a * poww(a * a % md, b / 2, md) % md : poww(a * a % md, b / 2, md) % md));
}
const ll MAXN = 1e6 + 10;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; // 998244353; // 1e9 + 9;
struct Node {
Node *L, *R;
int val = 0;
Node(int t_val): L(nullptr), R(nullptr), val(t_val) {};
Node(Node* L, Node* R): L(L), R(R), val(0) {
if (L) val += L -> val;
if (R) val += R -> val;
}
};
Node* Build(int L, int R) {
if (L == R) return new Node(0);
int mid = (L + R) >> 1;
return new Node(Build(L, mid), Build(mid + 1, R));
}
int Query(Node* v, int L, int R, int ql, int qr) {
if (ql > qr) return 0;
if (L == ql && R == qr) return v -> val;
int mid = (L + R) >> 1;
return Query(v -> L, L, mid, ql, min(mid, qr)) + Query(v -> R, mid + 1, R, max(ql, mid + 1), qr);
}
Node* Update(Node* v, int L, int R, int ind, int val) {
if (L == R) return new Node(val);
int mid = (L + R) >> 1;
if (ind <= mid) return new Node(Update(v -> L, L, mid, ind, val), v -> R);
else return new Node(v -> L, Update(v -> R, mid + 1, R, ind, val));
}
Node* PST[MAXN];
int n, q;
vector<pll> v;
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> q;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
v.push_back({x, i});
}
sort(all(v));
PST[n] = Build(1, n);
for (int i = n - 1; i >= 0; i--) PST[i] = Update(PST[i + 1], 1, n, v[i].Y, 1);
while (q--) {
int tL, tR;
cin >> tL >> tR;
int L = 1, R = n;
while (L < R) {
int mid = (L + R + 1) >> 1;
int ind = lower_bound(all(v), make_pair(1ll * mid, 0ll)) - v.begin();
int cnt = Query(PST[ind], 1, n, tL, tR);
if (cnt >= mid) L = mid;
else R = mid - 1;
}
cout << L << endl;
}
return 0;
}
