RT，发现好像查询为1 1 1时才能输出正确答案，其他的都会输出INF。

#include<iostream>
using namespace std;
struct node{
	int ls,rs,sum;
}tree[3500000];
int tot=1,n,m,root[1000001];
const int INF=1e9;
void update(int &o,int p,int l,int r,int x){
	tree[o=++tot]=tree[p];
	tree[o].sum++;
	if(l==r){
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid)update(tree[o].ls,tree[p].rs,l,mid,x);
	else update(tree[o].rs,tree[p].rs,mid+1,r,x);
	return;
}
int query(int p,int o,int l,int r,int k){
	if(l==r)return l;
	int mid=(l+r)>>1;
	int sum=tree[tree[o].ls].sum-tree[tree[p].ls].sum;
	if(k<=sum)return query(tree[p].ls,tree[o].ls,l,mid,k);
	else return query(tree[p].rs,tree[o].rs,mid+1,r,k-sum);
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		update(root[i],root[i-1],-INF,INF,x);
	}
	for(int i=1;i<=m;i++){
		int l,r,k;
		cin>>l>>r>>k;
		cout<<query(root[l-1],root[r],-INF,INF,k)<<endl;
	}
	return 0;
}