#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 N;
ll vals[50005*4 + 3];
sum_node (ll _N) {
N = _N;
for (ll i=0; i<_N; i++) {
vals[i] = 0;
}
}
void increment(ll idx, ll v, ll s, ll e, ll node) {
if (s==e) {
// leaf
//cout << "INCREMENTED AT NODE " << node << endl;
vals[node] += v;
return;
} else if (idx > (s+e)/2 ) {
increment(idx, v, (s+e)/2 + 1, e, node*2 +1);
} else {
increment(idx, v, s, (s+e)/2, node*2);
}
vals[node] = vals[node*2] + vals[node*2 + 1];
}
ll sum(ll x, ll y, ll s, ll e, ll node) { // inclusive of both
if ((x>y) || (x>e) || (y<s)) return 0; // invalid input
if (s==e) {
//cout << "PROVIDING VALUE " << x << ' ' << y << " AT NODE " << node << endl;
return vals[node];
}
// if completely within range
if ((x<=s) && (e<=y)) return vals[node];
return sum(x, y, s, (s+e)/2, node*2) + sum(x, y, (s+e)/2 + 1, e, node*2 + 1);
}
};
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(50005); // 1-indexed
}
void update (ll idx, ll v) {
if (s==e) {
// leaf.
counts->increment(v, 1, 1, 50005, 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, 1, 50005, 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, 50004, 1, 50005, 1);
}
// if completely within range
if ((s>=x) && (e<=y)) {
return counts->sum(h, 50004, 1, 50005, 1);
}
// 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->sum(i, i, 1, 50005, 1) << ' ';
}
cout << endl;
cout << "VALS: ";
for (ll i=0; i<N*4+3; i++) {
cout << root->counts->vals[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;
//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;
}
