#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#define inf 1012345678
using namespace std;
int n,q,a[100005],l[100005],r[100005],k[100005];
int ans_l[100005],ans_r[100005];
namespace ST{
	int log_2[100005],mn[20][100005];
	void init(){
		for (int i=2;i<=n;i++)log_2[i]=log_2[i/2]+1;
		for (int i=1;i<=n;i++)mn[0][i]=i;
		for (int w=1;(1<<w)<=n;w++)
			for (int i=1;i+(1<<w)-1<=n;i++)
				if (a[mn[w-1][i]]<a[mn[w-1][i+(1<<(w-1))]])mn[w][i]=mn[w-1][i];
				else mn[w][i]=mn[w-1][i+(1<<(w-1))];
		return;
	}
	int ask(int l,int r){
		if (l>r)return 0;
		int w=log_2[r-l+1];
		int id1=mn[w][l],id2=mn[w][r-(1<<w)+1];
		if (a[id1]<a[id2])return id1;
		return id2;
	}
}
bool check(){
	for (int i=1;i<=q;i++)
		if (ans_l[i]!=ans_r[i])return 0;
	return 1;
}
struct node{
	int id,val;
	bool operator <(const node &y)const{
		return val<y.val;
	}
}c[100005],d[100005];
namespace BIT{
	int tree[100005];
	void clear(){
		memset(tree,0,sizeof(tree));
		return;
	}
	void add(int p,int v){
		while(p<=n)tree[p]+=v,p+=(p&(-p));
		return;
	}
	int ask(int p){
		int ans=0;
		while(p)ans+=tree[p],p-=(p&(-p));
		return ans;
	}
}
namespace DS{
	set<int> f0;
	int pre(int x){
		set<int>::iterator it=f0.lower_bound(x);
		if ((*it)>x)it--;
		return (*it);
	}
	int nxt(int x){
		return *(f0.lower_bound(x));
	}
	set<node> f1;
	int j,last;
	void init(){
		BIT::clear();
		f0.clear(),f1.clear();
		f0.insert(0),f0.insert(n+1);
		j=1,last=-1;
		return;
	}
	node qwq(int l,int r){
		int p=ST::ask(l,r);
		node ans;
		ans.id=p,ans.val=a[p]+max(a[l-1],a[r+1]);
		return ans;
	}
	void ins(int x){
		int l=pre(x),r=nxt(x);
		if (l+1<=r-1){
			node awa=qwq(l+1,r-1);
			if (awa.val>last)f1.erase(awa);
			else BIT::add(awa.id,-1);
		}
		f0.insert(x);
		BIT::add(x,1);
		if (l+1<=x-1){
			node awa=qwq(l+1,x-1);
			if (awa.val>last)f1.insert(awa);
			else BIT::add(awa.id,1);
		}
		if (x+1<=r-1){
			node awa=qwq(x+1,r-1);
			if (awa.val>last)f1.insert(awa);
			else BIT::add(awa.id,1);
		}
		return;
	}
	int ask(int l,int r,int v){
		int ans=0;
		while(j<=n&&2*c[j].val<=v)ins(c[j].id),j++;
		while(f1.begin()!=f1.end()&&(*f1.begin()).val<=v){
			BIT::add((*f1.begin()).id,1);
			f1.erase(f1.begin());
		}
		int x=nxt(l),y=pre(r);
		if (x>y){
			if (a[ST::ask(l,r)]<=x)ans=1;
			else ans=0;
		}
		else{
			ans=BIT::ask(y)-BIT::ask(x-1);
			if (min(a[ST::ask(l,x-1)],a[ST::ask(y+1,r)])+max(a[x],a[y])<=v)ans++;
		}
		last=v;
		return ans;
	}
}
int main(){
	scanf("%d%d",&n,&q);
	for (int i=1;i<=n;i++)scanf("%d",&a[i]),c[i].val=a[i],c[i].id=i;
	a[0]=a[n+1]=inf;
	for (int i=1;i<=q;i++)scanf("%d%d%d",&l[i],&r[i],&k[i]),ans_l[i]=0,ans_r[i]=2*inf;
	ST::init();
	sort(c+1,c+1+n);
	while(!check()){
		for (int i=1;i<=q;i++){
			d[i].id=i;
			d[i].val=(0ll+ans_l[i]+ans_r[i])/2;
		}
		sort(d+1,d+1+q);
		DS::init();
		for (int i=1;i<=q;i++){
			int id=d[i].id;
			if (ans_l[id]==ans_r[id])continue;
			if (DS::ask(l[id],r[id],d[i].val)>=k[id])ans_r[id]=(0ll+ans_l[id]+ans_r[id])/2;
			else ans_l[id]=(0ll+ans_l[id]+ans_r[id])/2+1;
		}
	}
	for (int i=1;i<=q;i++)printf("%d\n",ans_l[i]);
	return 0;
}