#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define ll long long
ll N, Q;
ll p[200005];
struct sum_node {
// point update range query sum segment tree
ll s, e, m, val;
sum_node *l, *r;
sum_node (int _s, int _e):
s(_s), e(_e), m((_s+_e)/2), val(0) {
if (s != e) {
// not leaf
l = new sum_node(s, m);
r = new sum_node(m+1, e);
}
}
void increment(ll idx, ll v) {
if (s==e) {
// leaf
val += v;
return;
} else if (idx>m) {
r->increment(idx, v);
} else {
l->increment(idx, v);
}
val = l->val + r->val;
}
ll sum(ll x, ll y) { // inclusive of both
if ((x>y) || (x>e) || (y<s)) return 0; // invalid input
if (s==e) return val;
// if completely within range
if ((x<s) && (y>e)) return val;
return l->sum(x, y) + r->sum(x, y);
}
};
struct node {
ll s, e, m;
//int counts[200005];
sum_node *counts;
node *l, *r;
node (int _s, int _e) :
s(_s), e(_e), m((_s+_e)/2) {
if (s != e) { //not leaf node
l = new node(s, m);
r = new node(m+1, e);
}
//for (int i=0; i<200005; i++) counts[i]=0;
counts = new sum_node(0, 50005);
}
void update (ll idx, ll v) {
if (s==e) {
// leaf.
counts->increment(v, 1);
return;
} else if (idx>m) {
r->update(idx, v);
} else {
l->update(idx, v);
}
// this is a counts segment tree...
counts->increment(v, 1); // haha it's actually just this
}
ll get_h_cnt(ll h, ll x, ll y) { // inclusive of both endpoints
// sum of all the counts[h].
if ((x>y) || (x>e) || (y<s)) return 0; // invalid
if (x==y) { // leaf
return counts->sum(h, 50005);
}
// if completely within range
if ((s>=x) && (e<=y)) {
return counts->sum(h, 50005);
}
// else, consider children
return r->get_h_cnt(h, x, y) + l->get_h_cnt(h, x, y); // if out of range it'll return 0 so this is fine
}
bool try_h(ll h, ll x, ll y) {
return get_h_cnt(h, x, y) >= h;
}
} *root;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> N >> Q;
root = new node(1, N);
for (ll i=0; i<N; i++) {
cin >> p[i];
root->update(i+1, p[i]);
}
/*cout << "COUNTS: ";
for (ll i=0; i<N; i++) {
cout << root->counts[i] << ' ';
}
cout << endl;*/
ll l, r;
ll low, high, mid;
for (ll q=0; q<Q; q++) {
cin >> l >> r;
low = 0;
high = r-l+1;
while (high-low > 1) {
mid = (high+low)/2;
//cout << "TRY H=" << mid << "; COUNT=" << root->get_h_cnt(mid, l, r) << endl;
if (root->try_h(mid, l, r)) {
// means that mid is okay
low = mid; // so low is guaranteed okay, as try_h(mid) or 0 (0 is always attainable)
} else {
high = mid;
}
}
if (root->try_h(high, l, r)) {
// if high works too, then just swap w low. in the end, low wld the the one we use
swap(low, high);
}
// low is the answer
cout << low << '\n';
}
return 0;
}
