#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<ctime>
#include<map>
#define ll long long
#define MAXN 20105
#define uns unsigned
#define INF 0x3f3f3f3f
#define MOD 1000000007ll
#define lowbit(x) ((x)&(-(x)))
using namespace std;
inline ll read(){
	ll x=0;bool f=1;char s=getchar();
	while((s<'0'||s>'9')&&s>0){if(s=='-')f^=1;s=getchar();}
	while(s>='0'&&s<='9')x=(x<<1)+(x<<3)+s-'0',s=getchar();
	return f?x:-x;
}
int n,q,a[MAXN],st[MAXN][20],dp[MAXN][20][35],lg[MAXN];
int A[35],B[35],tmp[35];
inline int maxx(int x,int y){return x+a[x]>y+a[y]?x:y;}
inline int rmq(int l,int r){
	if(l>r)return 0;r=min(r,n);int k=lg[r-l+1];
	return maxx(st[l][k],st[r-(1<<k)+1][k]);
}
signed main()
{
	n=read(),q=read();
	for(int i=1;i<=n;i++)a[i]=read(),st[i][0]=i;
	lg[1]=0;
	for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1;
	for(int i=n;i>0;i--)
		for(int j=1;i+(1<<j)-1<=n;j++)
			st[i][j]=maxx(st[i][j-1],st[i+(1<<(j-1))][j-1]);
	for(int i=1;i<=n;i++)
		for(int k=0;k<=30;k++)dp[i][0][k]=i+a[i]+k;
	for(int j=0;j<lg[n];j++)
		for(int i=1;i<=n;i++)
			for(int k=0;k<=30;k++){
				for(int l=k;l<=30;l++)
					dp[i][j+1][l]=max(dp[i][j+1][l],dp[ rmq(i,dp[i][j][k]) ][j][l-k]);
				for(int l=k;l<=30;l++)
					dp[i][j+1][l]=max(dp[i][j+1][l],dp[i][j+1][k]+l-k);
			}
	while(q--){
		int l=read(),r=read(),k=read();
		if(l==r){printf("0\n");continue;}
		if(r<=l+a[l]+k){printf("1\n");continue;}
		int ans=2;
		for(int i=0;i<=k;i++)A[i]=l+a[l]+i;
		for(int e=lg[r-l+1];e>=0;e--){
			for(int i=0;i<=k;i++)tmp[i]=A[i],B[i]=rmq(l,A[i]);
			bool off=0;
			for(int i=0;i<=k&&!off;i++)
				for(int j=i;j<=k&&!off;j++)
					if(dp[B[i]][e][j-i]>tmp[j]){
						tmp[j]=dp[B[i]][e][j-i];
						if(tmp[j]>=r)off=1;
					}
			if(off)continue;ans+=(1<<e);
			for(int i=0;i<=k;i++)A[i]=tmp[i];
		}
		printf("%d\n",ans);
	}
	return 0;
}
