#include <bits/stdc++.h>
using namespace std;
const int offset = (1 << 18);
struct st{
vector <long long> vec[offset * 2];
void insert (long long a, long long b) {
a += offset;
while (a) {
vec[a].push_back(b);
a /= 2;
}
}
void init() {
for (int i = 0; i < offset * 2; i++) sort(vec[i].begin(), vec[i].end());
}
long long get(long long id, long long l, long long r, long long a, long long b, long long x) {
if (l > b || r < a) return 0;
if (l >= a && r <= b) return (lower_bound(vec[id].begin(), vec[id].end(), x)) - vec[id].begin();
long long mid = (l + r) / 2;
return get(id * 2, l, mid, a, b, x) + get(id * 2 + 1, mid + 1, r, a, b, x);
}
}segTree;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
long long n, q;
cin >> n >> q;
long long a[n + 1];
for (int i = 1; i <= n; i++){
long long x;
cin >> x;
a[i] = x;
segTree.insert(i, x);
}
segTree.init();
while (q--) {
long long l, r;
cin >> l >> r;
long long lo = 1, hi = 1e9, res = -1;
while (lo <= hi) {
long long mid = lo + (hi - lo) / 2;
long long cntx = r - l + 1 - segTree.get(1, 0, offset - 1, l, r, mid);
if (cntx >= mid) {
lo = mid + 1;
res = mid;
}
else hi = mid - 1;
}
cout << res << "\n";
}
return 0;
}
