求条

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
struct Segment_Tree
{
	int ls,rs,sum;
}tree[N*20];
int tot,root[N];
void update(int &id,int l,int r,int p)
{
	if(l>p||r<p)return;
	tree[++tot]=tree[id];
	id=tot;
	tree[id].sum++;
	if(l==r)return;
	int mid=l+r>>1;
	update(tree[id].ls,l,mid,p);
	update(tree[id].rs,mid+1,r,p);
}
int query(int idx,int idy,int l,int r)
{
	if(l==r)return l;
	int mid=l+r>>1;
	if(tree[tree[idy].ls].sum-tree[tree[idx].ls].sum<mid-l+1)return query(tree[idx].ls,tree[idy].ls,l,mid);
	return query(tree[idx].rs,tree[idy].rs,mid+1,r);
}
signed main()
{
	int n,Q;
	cin>>n>>Q;
	for(int i=1,x;i<=n;i++)
	{
		cin>>x;
		update(root[i]=root[i-1],0,N,x);
	}
	while(Q--)
	{
		int l,r;
		cin>>l>>r;
		cout<<query(root[l-1],root[r],0,N)<<"\n";
	}
    return 0;
}