rt，只有#1AC

#include<bits/stdc++.h>
#define int long long
#define N 1000005
#define INF 1e18
namespace IO{
	template<typename T> inline void write(T x){
		if(x<0) putchar('-'),x=-x;
		if(x==0){
			putchar('0'); return ;
		}
		if(x>9) write(x/10);
		putchar(x%10+'0');
		return ;
	}
	template<typename T> inline void read(T &x){
		x=0; int w=1; char ch=getchar();
		while(!isdigit(ch)){
			if(ch=='-') w=-1; ch=getchar();
		}
		while(isdigit(ch))
			x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
		x*=w; return ;
	}
}
using namespace IO;
using namespace std;
struct tree{
	int ls,rs,v,l,r;
}t[N<<4];
int n,m,a[N],b[N],cnt,tot,rt[N];
void build(int &p,int l,int r){
	p=++cnt,t[p].l=l,t[p].r=r;
	if(l==r) return;
	int mid=l+r>>1;
	build(t[p].ls,l,mid);
	build(t[p].rs,mid+1,r);
}
void change(int &p,int q,int x){
	p=++cnt,t[p]=t[q],t[p].v++;
	if(t[p].l==t[p].r) return;
	int mid=t[p].l+t[p].r>>1;
	if(x<=mid) change(t[p].ls,t[q].ls,x);
	else change(t[p].rs,t[q].rs,x);
}
int query(int p,int q,int x){
	if(t[p].l==t[p].r) return a[t[p].l];
	int k=t[t[q].ls].v-t[t[p].ls].v;
	if(k>=x) return query(t[p].ls,t[q].ls,x);
	else return query(t[p].rs,t[q].rs,x-k);
}
signed main(){
	read(n),read(m);
	for(int i=1;i<=n;i++) read(a[i]),b[i]=a[i];
	sort(b+1,b+n+1);
	tot=unique(b+1,b+n+1)-(b+1);
	build(rt[0],1,tot);
	for(int i=1,k;i<=n;i++){
		k=lower_bound(b+1,b+tot+1,a[i])-b;
		change(rt[i],rt[i-1],k);
	}
	int l,r,k;
	while(m--){
		read(l),read(r),read(k);
		write(query(rt[l-1],rt[r],k)),putchar('\n');
	}
	return 0;
}