rt，代码：

#include<bits/stdc++.h>
#define ri register int
#pragma G++ optimize(3)
using namespace std;
struct node{
	int l,r,ln,rn,sum;
}tree[6300010];
vector<int>b;
int a[300010],n,m,root[3000010],idx=0;
void u(int k)
{
	tree[k].sum=tree[tree[k].ln].sum+tree[tree[k].rn].sum;
}
void build(int k,int l,int r)
{
	tree[k].l=l,tree[k].r=r;
	if(l==r)return;
	int mid=(l+r)>>1;
	tree[k].ln=++idx,tree[k].rn=++idx;
	build(tree[k].ln,l,mid);
	build(tree[k].rn,mid+1,r);
	u(k);
}
void update(int p,int k,int i)
{
	tree[k].l=tree[p].l,tree[k].r=tree[p].r,tree[k].rn=tree[p].rn,tree[k].ln=tree[p].ln,tree[k].sum=tree[p].sum;
	if(tree[k].l==tree[k].r)
	{
		tree[k].sum++;
		return;
	}
	int mid=(tree[k].l+tree[k].r)>>1;
	if(i<=mid)tree[k].ln=++idx,update(tree[p].ln,tree[k].ln,i);
	else tree[k].rn=++idx,update(tree[p].rn,tree[k].rn,i);
	u(k);
}
int query(int p,int k,int L,int R)
{
	if(tree[k].l>=L&&tree[k].r<=R)
	{
		return tree[k].sum-tree[p].sum;
	}
	int mid=(tree[k].l+tree[k].r)>>1,ans=0;
	if(L<=mid)ans+=query(tree[p].ln,tree[k].ln,L,R);
	if(mid+1<=R)ans+=query(tree[p].rn,tree[k].rn,L,R);
	return ans;
}
int main ()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++){
	scanf("%d",&a[i]);
	b.push_back(a[i]);}
	sort(b.begin(),b.end()); 
	b.erase(unique(b.begin(),b.end()),b.end());
	for(int i=1;i<=n;i++)
	{
		a[i]=lower_bound(b.begin(),b.end(),a[i])-b.begin()+1;
	}
	
	root[0]=++idx;
	build(root[0],1,b.size());
	for(int i=1;i<=n;i++)
	{
		root[i]=++idx;
		update(root[i-1],root[i],a[i]);
	}
	for(int i=1;i<=m;i++)
	{
		int l,r,k;
		scanf("%d%d%d",&l,&r,&k);
		int ll=0,rr=b.size();
		while(ll<rr)
		{
			int mid=(ll+rr+1)>>1;
			if(query(root[l-1],root[r],1,mid)<k)ll=mid;
			else rr=mid-1;
		}
		printf("%d\n",b[ll]);
	}
    return 0;
}