区间第K大
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
typedef long long ll;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
} /********************************************************************/ const int maxn = 1e5+;
int n, m, cnt, root[maxn], a[maxn], x, y, k; struct node{
int l, r, sum;
}T[maxn*]; vector<int>v;
int getid(int x){return lower_bound(v.begin(), v.end(), x) - v.begin() + ;} //离散化 void update(int l, int r, int &x, int y, int pos){
T[++cnt] = T[y], T[cnt].sum++, x = cnt;
if(l == r) return ;
int mid = (l+r)>>;
if(mid >= pos) update(l, mid, T[x].l, T[y].l, pos);
else update(mid+, r, T[x].r, T[y].r, pos);
} int query(int l, int r, int x, int y, int k){
if(l == r) return l;
int mid = (l+r)>>;
int sum = T[T[y].l].sum - T[T[x].l].sum;
if(sum >= k) return query(l, mid, T[x].l, T[y].l, k);
else return query(mid+, r, T[x].r, T[y].r, k-sum);
} int main(){
n = read(); m = read();
for(int i = ;i <= n;i++){
a[i] = read();
v.push_back(a[i]);
}
//离散化
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
//unique 去重
for(int i = ;i <= n;i++) update(, n, root[i], root[i-], getid(a[i]));
for(int i = ;i <= m;i++){
x = read(); y = read(); k = read();
printf("%d\n", v[query(, n, root[x-], root[y], k) - ]); //离散化回来
}
return ;
}