#include <bits/stdc++.h>
#define MP(a,b) make_pair((a),(b)) 
#define fi first
#define se second
using namespace std;
int T,n,m=30,q;
int to[20][20010][33],lg2[20010],r[20010],dp[33],tmp[33];
pair<int,int>st[20][20010];
int qry(int l,int r){
	int lll=lg2[r-l];
	return max(st[lll][l],st[lll][r-(1<<lll)+1]).se;
}
int main(){
	scanf("%d%d",&n,&q);
	for(int i=1,w;i<=n;i++) scanf("%d",&w),st[0][i]=MP(r[i]=min(i+w,n),i);
	for(int i=2;i<=n;i++) lg2[i]=lg2[i>>1]+1;
	for(int j=1;j<=lg2[n];j++) for(int i=1;i<=n;i++){
		if(i+(1<<j)-1>n) break;
		st[j][i]=max(st[j-1][i],st[j-1][i+(1<<(j-1))]);
	}
	for(int i=1;i<=n;i++) for(int k=0;k<=m;k++) to[0][i][k]=min(n,r[i]+k);
	for(int j=1;j<=lg2[n];j++) for(int i=1;i<=n;i++) for(int k=0;k<=m;k++) for(int l=0;l<=k;l++){
		to[j][i][k]=max(to[j][i][k],to[j-1][qry(i,to[j-1][i][l])][k-l]);
	}
	while(q--){
		int L,R,k,res=0;
		scanf("%d%d%d",&L,&R,&k);
		if(L==R){
			puts("0");
			continue;
		}
		if(r[L]+k>=R){
			puts("1");
			continue;
		}
		for(int i=0;i<=k;i++) dp[i]=L;
		for(int j=lg2[n];j>=0;j--){
			for(int i=0;i<=k;i++) tmp[i]=dp[i];
			for(int i=0;i<=k;i++){
				int p=qry(L,dp[i]);
				for(int l=0;i+l<=k;l++) tmp[i+l]=max(tmp[i+l],to[j][p][l]);
			}
			int falg=true;
			for(int i=0;i<=k;i++) falg&=(tmp[i]<R);
			if(!falg) continue;
			for(int i=0;i<=k;i++) dp[i]=tmp[i];
			res+=1<<j;
		}
		printf("%d\n",res+1);
	}
}
