record

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
typedef long long LL;
typedef pair<int,int>PII;
const int N=2e5+10; 
int n,m;
int a[N]; 
struct query{
	int l,r,k;
}q[N];
int l[N],r[N],mid[N];
int tr[N];
void init(){
	memset(tr,0,sizeof tr);
}
void add(int x,int k){
	for(;x<=n;x+=x&-x)tr[x]+=k;
}
int ask(int x){
	int res=0;
	for(;x;x-=x&-x)res+=tr[x];
	return res;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		q[i]={x,y,z};
		l[i]=0,r[i]=1e9;
	}
	while(1){
		vector<PII>vec;
		int flag=1;
		for(int i=1;i<=m;i++){
			if(l[i]!=r[i]){
				mid[i]=(l[i]+r[i])>>1;
				flag=0;
				vec.push_back({mid[i],i+n});
			}
		}
		if(flag)break;
		for(int i=1;i<=n;i++)vec.push_back({a[i],i});
		sort(vec.begin(),vec.end());
		init();
		for(int i=0;i<vec.size();i++){
			int id=vec[i].second;
			if(id<=n){
				add(id,1);
			}
			else{
				id-=n;
				int ans=ask(q[id].r)-ask(q[id].l-1);
				if(ans>=q[id].k)r[id]=mid[id];
				else l[id]=mid[id]+1;
			}
		}
	}
	for(int i=1;i<=m;i++)cout<<l[i]<<'\n';
	return 0;
}