#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#define ST first
#define ND second
#define PB push_back
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;
typedef tree<pi,null_type,less<pi>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
const int nax = 200 * 1000 + 10, INF = 1e9;
int n, q;
int val[nax], l[nax], r[nax], mid[nax], ans[nax];
pi prz[nax];
vi contain[nax];
ordered_set S;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> q;
for(int i = 1; i <= n; ++i) {
cin >> val[i];
}
for(int i = 1; i <= q; ++i) {
cin >> prz[i].ST >> prz[i].ND;
l[i] = 1; r[i] = prz[i].ND - prz[i].ST + 1;
mid[i] = (l[i] + r[i]) / 2;
contain[prz[i].ST - 1].PB(-i);
contain[prz[i].ND].PB(i);
}
for(int rep = 0; ; ++rep) {
S.clear();
int id = 1;
for(int i = 0; i <= n; ++i) {
if(i > 0) {
S.insert({-val[i], id++});
}
for(auto x : contain[i]) {
if(x < 0) {
ans[-x] = -S.order_of_key({-mid[-x], INF});
} else {
ans[x] += S.order_of_key({-mid[x], INF});
}
}
}
bool any = false;
for(int i = 1; i <= q; ++i) {
if(l[i] <= r[i]) {
if(ans[i] >= mid[i]) {
l[i] = mid[i] + 1;
} else {
r[i] = mid[i] - 1;
}
mid[i] = (l[i] + r[i]) / 2;
any = true;
}
}
if(!any) break;
}
for(int i = 1; i <= q; ++i) {
cout << l[i] - 1 << "\n";
}
}
