//#include <bits/stdc++.h>
//using namespace std;
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#include <cstdio>

#define rep(i,_l,_r) for(signed i=(_l),_end=(_r);i<=_end;++i)
#define fep(i,_l,_r) for(signed i=(_l),_end=(_r);i>=_end;--i)
#define print(x,y) write(x),putchar(y)

template <class T> inline T read(const T sample) {
    T x=0; int f=1; char s;
    while((s=getchar())>'9'||s<'0') if(s=='-') f=-1;
    while(s>='0'&&s<='9') x=(x<<1)+(x<<3)+(s^48),s=getchar();
    return x*f;
}
template <class T> inline void write(const T x) {
    if(x<0) return (void) (putchar('-'),write(-x));
    if(x>9) write(x/10);
    putchar(x%10^48);
}
template <class T> inline T Max(const T x,const T y) {if(x>y) return x; return y;}
template <class T> inline T Min(const T x,const T y) {if(x<y) return x; return y;}

const int maxn=2e4+4;

int n,q,lg[maxn],a[maxn],st[32][18][maxn],dp[18][32][maxn],ans[maxn],f[maxn][32],tmp[32];
struct node {
	int l,r,k;
} s[maxn];

void init() {
	rep(i,2,n) lg[i]=lg[i>>1]+1;
}

int Query(int k,int l,int r) {
	int d=lg[r-l+1];
	return Max(st[k][d][l],st[k][d][r-(1<<d)+1]);
}

int main() {
	n=read(9),q=read(9); init();
	int lgn=lg[n]+1;
	rep(i,1,n) a[i]=read(9);
	rep(k,0,30) rep(i,1,n) dp[0][k][i]=Min(n,i+a[i]+k);
	rep(j,1,lgn) {
		rep(k,0,30) rep(i,1,n) st[k][0][i]=dp[j-1][k][i];
		rep(k,0,30) rep(i,1,lgn) rep(p,1,n)
			if(p+(1<<i)-1<=n)
				st[k][i][p]=Max(st[k][i-1][p],st[k][i-1][p+(1<<i-1)]);
			else break;
		rep(k1,0,30) rep(k2,0,30) {
			if(k1+k2>30) break;
			rep(i,1,n) dp[j][k1+k2][i]=Max(dp[j][k1+k2][i],Query(k1,i,dp[j-1][k2][i]));
		}
	}
	rep(i,1,q) {
		s[i].l=read(9),s[i].r=read(9),s[i].k=read(9);
		if(s[i].l==s[i].r) ans[i]=-1;
		else rep(j,0,s[i].k) f[i][j]=s[i].l;
	}
	fep(j,lgn,0) {
		rep(k,0,30) rep(i,1,n) st[k][0][i]=dp[j][k][i];
		rep(k,0,30) rep(i,1,lgn) rep(p,1,n)
			if(p+(1<<i)-1<=n)
				st[k][i][p]=Max(st[k][i-1][p],st[k][i-1][p+(1<<i-1)]);
			else break;
		rep(i,1,q) {
			if(ans[i]==-1) continue;
			rep(k,0,s[i].k) tmp[k]=0;
			rep(k1,0,s[i].k) rep(k2,0,s[i].k) {
				if(k1+k2>s[i].k) break;
				tmp[k1+k2]=Max(tmp[k1+k2],Query(k1,s[i].l,f[i][k2]));
			}
			if(tmp[s[i].k]<s[i].r) {
				ans[i]+=(1<<j);
				rep(k,0,s[i].k) f[i][k]=tmp[k];
			}
		}
	}
	rep(i,1,q) print(ans[i]+1,'\n');
	return 0;
}

