1 #include 
     
       2 #define read read() 3 #define up(i,l,r) for(int i = (l);i <= (r);i++) 4 using namespace std; 5 int read 6 { 7     int x = 0,f = 1; char ch = getchar(); 8     while(ch < 48 || ch > 57) {
   if(ch == '-') f = -1; ch = getchar();} 9     while(ch >=48 && ch <=57) {x = 10 * x + ch - 48; ch = getchar();}10     return x * f;11 }12 const int N = 2e5+7;13 struct a14 {15     int l,r,sum;16 }node[N*25];17 int n,m,cnt,a[N],root[N];18 vector
      
        v;19 int Get_id(int x) {
   return lower_bound(v.begin(),v.end(),x) - v.begin() + 1;}20 void update(int l,int r,int &cur,int pre,int pos)21 {22     node[++cnt] = node[pre],node[cnt].sum++,cur = cnt;23     if(l==r) return;24     int mid = (l+r)>>1;25     if(pos<=mid) update(l,mid,node[cur].l,node[pre].l,pos);26     else update(mid+1,r,node[cur].r,node[pre].r,pos);27 }28 int query(int l,int r,int x,int y,int k)29 {30     if(l==r) return l;31     int mid = (l+r)>>1;32     int lsum = node[node[y].l].sum - node[node[x].l].sum;33     if(lsum>=k) return query(l,mid,node[x].l,node[y].l,k);34     else return query(mid+1,r,node[x].r,node[y].r,k-lsum);35 }36 int main()37 {38     freopen("input.txt","r",stdin);39     n = read; m = read;40     int l,r,k;41     up(i,1,n) a[i] = read,v.push_back(a[i]);42     sort(v.begin(),v.end());43     v.erase(unique(v.begin(),v.end()),v.end());44     up(i,1,n) update(1,n,root[i],root[i-1],Get_id(a[i]));45     up(i,1,m)46     {47         l = read; r = read; k = read;48         printf("%d\n",v[query(1,n,root[l-1],root[r],k)-1]);49     }50     return 0;51 }