#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,mx;
int val[nax], l[nax], r[nax], mid[nax], ans[nax];
pi prz[nax];
vi contain[nax];
int T[nax];
void add(int a, int x) {
while(a > 0) {
T[a] += x;
a -= (a & (-a));
}
}
int ask(int a) {
int w = 0;
while(a < mx) {
w += T[a];
a += (a & (-a));
}
return w;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> q;
for(int i = 1; i <= n; ++i) {
cin >> val[i];
mx = max(mx, 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) {
for(int i = 0; i <= n; ++i) {
if(i > 0) {
add(val[i], 1);
}
for(auto x : contain[i]) {
if(x < 0) {
ans[-x] = -ask(mid[-x]);
} else {
ans[x] += ask(mid[x]);
}
}
}
for(int i = 1; i <= n; ++i) {
add(val[i], -1);
}
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";
}
}
