#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
#define pb push_back
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define TC int __TC__; cin >> __TC__; while(__TC__--)
#define ar array
const int INF = 1e9 + 7, N = 2e5;
int n, q;
struct node{
node* left = nullptr,* right = nullptr;
int v = 0;
};
node* root[N+1];
void build(node *rt, int lx, int rx){
if(lx == rx) return;
int m = lx+(rx-lx) / 2;
rt->left = new node;
rt->right = new node;
build(rt->left, lx, m);
build(rt->right, m+1, rx);
return;
}
void add(int pos, node* lr, node* nr, int lx, int rx){
if(lx == rx){
nr->v=1;
return;
}
int m = lx + (rx - lx) / 2;
if(pos <= m){ // go left
nr->right = lr->right;
nr->left = new node;
add(pos, lr->left, nr->left, lx, m);
}else{ // go right
nr->left = lr->left;
nr->right = new node;
add(pos, lr->right, nr->right, m+1, rx);
}
nr->v = nr->left->v + nr->right->v;
}
int get(int l, int r, node* rt, int lx, int rx){
if(r < lx || l > rx) return 0;
if(lx >= l && rx <= r) return rt->v;
int m = lx + (rx - lx) / 2;
return get(l, r, rt->left, lx, m) + get(l, r, rt->right, m+1, rx);
}
int main(void)
{
FAST;
cin >> n >> q;
vector<ar<int,2>> a(n);
for(int i = 0; i < n; ++i){
cin >> a[i][0];
a[i][1] = i+1;
}
sort(a.rbegin(), a.rend());
root[0] = new node;
build(root[0], 1, n);
for(int i = 1; i <= n; ++i){
root[i] = new node;
add(a[i-1][1], root[i-1], root[i], 1, n);
}
sort(a.begin(), a.end());
while(q--){
int l, r; cin >> l >> r;
int ans = 1;
for(int j = 22; j >= 0; --j){
int nans = ans + (1<<j);
auto it = lower_bound(a.begin(), a.end(), ar<int,2>{nans, 0});
if(it == a.end()) continue;
int pos = n-(it - a.begin());
if(get(l, r, root[pos], 1, n) >= nans) ans += (1<<j);
}
cout << ans << '\n';
}
return 0;
}
