RT，以下代码在 https://www.acwing.com/activity/content/code/content/9637930/ 是能过的，但在 Luogu 没过

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2000010;
struct node{int l,r,s;}t[N];
int n,m,tot,root[N],a[N],b[N];
int get(int x){return lower_bound(b+1,b+n+1,x)-b;}
int build(int l,int r){
    int p=++tot;
    if(l==r) return p;
    int mid=(l+r)/2;
    t[p]={build(l,mid),build(mid+1,r),0};
    return p;
}
int insert(int now,int l,int r,int x){
    int p=++tot;
    t[p]=t[now];
    if(l==r){
        t[p].s++;
        return p;
    }
    int mid=(l+r)/2;
    if(x<=mid) t[p].l=insert(t[now].l,l,mid,x);
    else t[p].r=insert(t[now].r,mid+1,r,x);
    t[p].s=t[t[p].l].s+t[t[p].r].s;
    return p;
}
int ask(int p,int q,int l,int r,int k){
    if(l==r) return l;
    int mid=(l+r)/2,x=t[t[p].l].s-t[t[q].l].s;
    if(k<=x) return ask(t[p].l,t[q].l,l,mid,k);
    else return ask(t[p].r,t[q].r,mid+1,r,k-x);
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[i]=a[i];
    }
    sort(b+1,b+n+1);
    int t=unique(b+1,b+n+1)-b-1;
    root[0]=build(1,t);
    for(int i=1;i<=n;i++) root[i]=insert(root[i-1],1,t,get(a[i]));
    for(int i=1;i<=m;i++){
        int l,r,k;
        cin>>l>>r>>k;
        cout<<b[ask(root[r],root[l-1],1,t,k)]<<endl;
    }
    return 0;
}