#include <bits/stdc++.h>
using namespace std;
const int N = 3e5+5;
struct tree{
struct node{
node *l,*r;
int sum;
node(int k) : sum(k),l(nullptr),r(nullptr) {}
node(node* l,node* r) : l(l),r(r) {
sum = (l?l->sum:0) + (r?r->sum:0);
}
node() : sum(0),l(nullptr),r(nullptr) {}
};
public:
typedef node* pnode;
pnode roots[N];
node* build(int l,int r) {
if(l==r)return new node(0);
int mid = (l+r)/2;
return new node(build(l,mid),build(mid+1,r));
}
node* upd(node* cur,int l,int r,int tar,int val) {
if(l>r)return 0;
if(l==r) return new node(val);
assert(cur);
int mid = (l+r)/2;
if(tar > mid) return new node(cur->l,upd(cur->r,mid+1,r,tar,val));
else return new node(upd(cur->l,l,mid,tar,val),cur->r);
}
int qry(node*cur,int l,int r,int ll,int rr) {
if(!cur)return 0;
if(l>r||r<ll|l>rr)return 0;
if(l>=ll&&r<=rr)return cur->sum;
int mid = (l+r)/2;
return qry(cur->l,l,mid,ll,rr) + qry(cur->r,mid+1,r,ll,rr);
}
}t;
int n,q,a,b;
int main() {
cin>>n>>q;
vector<int> v(n+1);
vector<int> freq(n+1);
for(int i = 1;i<=n;i++)cin>>v[i];
t.roots[0] = t.build(1,n);
for(int i = 1;i<=n;i++) {
freq[v[i]]++;
t.roots[i] = t.upd(t.roots[i-1],1,n,v[i],freq[v[i]]);
}
for(int i = 0;i<q;i++) {
cin>>a>>b;
// cout << a << " " << b << "\n";
int l = 1, r = n, ans;
while(l<=r) {
int mid = (l+r)/2;
int frq = t.qry(t.roots[b],1,n,mid,n) - t.qry(t.roots[a-1],1,n,mid,n);
// cout << frq << "\n";
if(frq >= mid) ans = mid, l = mid+1;
else r = mid - 1;
}
cout<<ans<<"\n";
}
}
/*
7 6
3 2 3 1 1 4 7
3 4
1 7
1 6
4 5
1 2
5 7
*/
