#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair <int , int>
#define arr3 array <int , 3>
using namespace std;
const int maxn = 2e5 + 7;
int n;
struct PST
{
struct node
{
int sum;
node *l_child; node *r_child;
node(node *x)
{
sum = x->sum;
l_child = x->l_child;
r_child = x->r_child;
}
node(int x)
{
sum = x;
l_child = r_child = NULL;
}
node(node *lnode , node *rnode)
{
sum = lnode->sum + rnode->sum;
l_child = lnode;
r_child = rnode;
}
} *root[maxn];
node *build(int l , int r)
{
if(l == r) return new node(0);
int mid = (l+r)>>1;
return new node(node(build(l , mid) , build(mid+1 , r)));
}
node *update(node *id , int l , int r , int pos , int val)
{
if(l == r)
{
node *cur = new node(id);
cur->sum += val;
return cur;
}
int mid = (l+r)>>1;
if(pos <= mid)
{
return new node(update(id->l_child , l , mid , pos , val) , id->r_child);
}
else
{
return new node(id->l_child , update(id->r_child , mid+1 , r , pos , val));
}
}
int get(node *id , int l , int r , int u , int v)
{
if(r < u || l > v) return 0;
if(u <= l && r <= v) return id->sum;
int mid = (l+r)>>1;
return get(id->l_child , l , mid , u , v) + get(id->r_child , mid+1 , r , u , v);
}
void add(int event)
{
root[event] = root[event-1];
}
void upd(int event , int pos , int val)
{
root[event] = update(root[event] , 1 , n , pos , val);
}
int gt(int event , int l , int r)
{
return get(root[event] , 1 , n , l , r);
}
} pst;
int p[maxn] , q;
void solve()
{
cin >> n >> q;
pst.root[0] = pst.build(1 , n);
for(int i = 1; i <= n; i++)
{
cin >> p[i];
pst.add(i);
pst.upd(i , p[i] , 1);
}
while(q--)
{
int l , r; cin >> l >> r;
int lo = 1 , hi = (r - l + 1) , ans = 1;
while(lo <= hi)
{
int mid = (lo + hi)>>1;
int chk = pst.gt(r , mid , n) - pst.gt(l-1 , mid , n);
if(chk >= mid)
{
ans = mid;
lo = mid + 1;
}
else hi = mid - 1;
}
cout << ans << '\n';
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
solve();
return 0;
}
