#include<algorithm> #include<iostream> #include<cstdio> using namespace std; struct data{ int l,r,sum; }node[3000000]; int n,m,cnt,tot,root[100010],a[100010],num[100010]; int find(int x){ int l=1,r=tot,Mid; while(l<=r){ Mid=(l+r)>>1; if(num[Mid]<x)l=Mid+1; else r=Mid-1; } return l; } void update(int pre,int &k,int l,int r,int v){ k=++cnt; node[k].sum=node[pre].sum+1; if(l==r)return; node[k].l=node[pre].l;node[k].r=node[pre].r; int mid=(l+r)>>1; if(v<=mid)update(node[pre].l,node[k].l,l,mid,v); else update(node[pre].r,node[k].r,mid+1,r,v); } int ask(int r1,int r2,int l,int r,int k){ if(l==r)return l; int left_sum=node[node[r2].l].sum-node[node[r1].l].sum; int mid=(l+r)>>1; if(left_sum>=k)return ask(node[r1].l,node[r2].l,l,mid,k); else return ask(node[r1].r,node[r2].r,mid+1,r,k-left_sum); } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); num[i]=a[i]; } sort(num+1,num+n+1); num[++tot]=num[1]; for(int i=2;i<=n;i++) if(num[i]!=num[i-1]) num[++tot]=num[i]; for(int i=1;i<=n;i++) update(root[i-1],root[i],1,tot,find(a[i])); for(int i=1;i<=m;i++){ int l,r,x; scanf("%d%d%d",&l,&r,&x); printf("%d\n",num[ask(root[l-1],root[r],1,tot,x)]); } return 0; }