// CPP program for querying in
// wavelet tree Data Structure
#include <bits/stdc++.h>
using namespace std;
#define N 200005
// Given Array
int a[N];
// wavelet tree class
struct wavelet_tree{
int lo, hi;
wavelet_tree *l, *r;
vector<int>b;
wavelet_tree(int *from, int *to, int x, int y){
lo = x, hi = y;
if(lo == hi || from >= to)return;
int mid = (lo + hi)/2;
auto f = [mid](int x){
return x <= mid;
};
b.reserve(to-from+1);
b.push_back(0);
for(auto it = from;it != to;it++){
b.push_back(b.back() + f(*it));
}
auto pivot = stable_partition(from, to, f);
l = new wavelet_tree(from, pivot, lo, mid);
r = new wavelet_tree(pivot, to, mid+1, hi);
}
int kth(int l, int r, int k){
if(l > r)return 0;
if(lo == hi)return lo;
int inleft = b[r] - b[l-1];
int lb = b[l-1];
int rb = b[r];
if(k <= inleft)return this->l->kth(lb+1, rb, k);
return this->r->kth(l-lb, r-rb, k-inleft);
}
};
// Driver code
int maxi, mini = 1e9;
int main()
{
ios::sync_with_stdio(0);cin.tie(0);
int n, q;cin >> n >> q;
for(int i=1;i<=n;i++)cin >> a[i];
wavelet_tree hi(a+1, a + 1 + n, 0, 2e5);
//cout << hi.kth(4, 5, 2) << '\n';
while(q--){
int l,r; cin >> l >> r;
int s = 0, e = r-l+1, ans = 0;
while(s <= e){
int m = (s + e)/2;
if(hi.kth(l, r, (r-l+1) - m + 1) >= m)ans = m, s = m + 1;
else e = m -1;
}
cout << ans << '\n';
}
// count of elements less than 2 in range [1,3]
//cout << obj.kOrLess(0, 3, 2) << '\n';
return 0;
}
