Here is my code.

#include<bits/stdc++.h>
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int N=2e5+5,NN=2e3+5;
int n,_,nn,a[N],l[N],r[N],qjj[N],l_,r_,mid,ans[N],tree[N],maxx;
struct cyl{int l,r;}qj[NN];
struct Mirko{int l,r,bh;}ques[N];
bool cmp(Mirko a,Mirko b){
	if(qjj[a.l]==qjj[b.l])return a.r<b.r;
	return a.l<b.l;
}
void add(int x,int y){for(int i=x;i<=maxx;i+=lowbit(i))tree[i]+=y;}
int query(int x){int ans=0;for(int i=x;i>=1;i-=lowbit(i))ans+=tree[i];return ans;}
int main(){
freopen("hack.in","r",stdin);freopen("index.out","w",stdout);
	scanf("%d%d",&n,&_);nn=sqrt(n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]),maxx=max(a[i],maxx);
	for(int i=1;i<=_;i++)scanf("%d%d",&ques[i].l,&ques[i].r),ques[i].bh=i;
	for(int i=1;i<=nn;i++)qj[i].l=(i-1)*nn+1,qj[i].r=i*nn;
	if(qj[nn].r!=n)qj[nn+1].l=qj[nn].r+1,qj[++nn].r=n;
	for(int i=1;i<=nn;i++)
		for(int j=qj[i].l;j<=qj[i].r;j++)qjj[j]=i;
	sort(ques+1,ques+_+1,cmp);
	for(int i=1;i<=_;i++){
		if(i==1||qjj[ques[i].l]!=qjj[ques[i-1].l]){
			memset(tree,0,sizeof(tree));
			for(int j=ques[i].l;j<=ques[i].r;j++)add(a[j],1);
		}else{
			if(ques[i].l>ques[i-1].l)for(int j=ques[i-1].l;j<ques[i].l;j++)add(a[j],-1);
			if(ques[i].l<ques[i-1].l)for(int j=ques[i].l;j<ques[i-1].l;j++)add(a[j],1);
			if(ques[i].r>ques[i-1].r)for(int j=ques[i-1].r+1;j<=ques[i].r;j++)add(a[j],1);
			if(ques[i].r<ques[i-1].r)for(int j=ques[i].r+1;j<ques[i-1].r;j++)add(a[j],-1);
		}
		l_=1;r_=ques[i].r-ques[i].l+1;
		while(l_<=r_){
			mid=(l_+r_)>>1;
			if(ques[i].r-ques[i].l+1-query(mid-1)>=mid)ans[ques[i].bh]=mid,l_=mid+1;
			else r_=mid-1;
		}
	}
	for(int i=1;i<=_;i++)printf("%d\n",ans[i]);
	return 0;
}

Obviously,it's $O(n\sqrt{n}\log n)$,so I hack it.

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,NN=2e3+5;
int n,_,nn,l_,r_;
struct cyl{int l,r;}qj[NN];
std::mt19937 rnd(20081108);//LC
int main(){
freopen("hack.in","w",stdout);
	n=100000;nn=sqrt(n);
	printf("%d %d\n",n,n);
	for(int i=1;i<n;i++)printf("%d ",rnd()%n+1);
	printf("%d\n",n);
	for(int i=1;i<=nn;i++)qj[i].l=(i-1)*nn+1,qj[i].r=i*nn;
	if(qj[nn].r!=n)qj[nn+1].l=qj[nn].r+1,qj[++nn].r=n;
	for(int i=1;i<nn;i++)
		for(int j=1;j<=nn/2;j++)
			if(j&1)printf("%d %d\n",qj[i].l,qj[i].r+j),printf("%d %d\n",qj[i].l,n),_+=2;
			else printf("%d %d\n",qj[i].r,qj[i].r+j),_++;
	while(_<n){
		l_=rnd()%n+1;r_=rnd()%n+1;
		if(l_>=r_)swap(l_,r_);
		printf("%d %d\n",l_,r_);
		_++;
	}
	return 0;
}

Becase no tj is hacked,so I won't @管理员.I just want to tell you that $O(n\sqrt{n}\log n)$ is wrong.