// iostream is too mainstream
#include <cstdio>
// bitch please
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <chrono>
#include <random>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <iomanip>
#define dibs reserve
#define OVER9000 1234567890LL
#define tisic 47
#define soclose 1e-8
#define patkan 9
#define ff first
#define ss second
using uint = unsigned int;
using cat = long long;
using dbl = long double;
constexpr dbl pi = 3.14159265358979323846;
using namespace std;

#ifdef DONLINE_JUDGE
	// palindromic tree is better than splay tree!
	#define lld I64d
#endif

template <typename T>
T abs(T x) { return (x < 0) ? (-x) : x; }

cat gcd(cat a, cat b) {
	if(a > b) swap(a, b);
	while(a) {
		cat c = b%a;
		b = a;
		a = c;
	}
	return b;
}

cat pw(cat a, cat e, cat mod) {
	if(e <= 0) return 1;
	cat x = pw(a, e/2, mod);
	x = x * x % mod;
	return (e&1) ? x * a % mod : x;
}

template <typename T>
class fin {
	int init_val;
	vector<T> node_val;

	int lastone(int x) { return x & (x ^ (x-1)); }

public:
	fin() {}

	fin(int N, T init_val_) : init_val{init_val_} {
		node_val.resize(N+10, init_val_);
	}

	void put(int pos, T val) {
		for(int i = pos+1; i < (int)node_val.size(); i += lastone(i))
			node_val[i] = max(node_val[i], val);
	}

	T get(int pos) {
		T ret = init_val;
		for(int i = pos+1; i > 0; i -= lastone(i))
			ret = max(ret, node_val[i]);
		return ret;
	}
};

struct query {
	int l, r, k, id;
};

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cout << fixed << setprecision(12);
	int N, Q;
	cin >> N >> Q;
	constexpr int K = 30;
	vector<int> A(N);
	for(int i = 0; i < N; i++) cin >> A[i];
	vector<int> ans(Q);
	vector< vector<query> > q_by_l(N);
	for(int q = 0; q < Q; q++) {
		int l, r, k;
		cin >> l >> r >> k;
		l--, r--;
		q_by_l[l].push_back({.l = l, .r = r, .k = k, .id = q});
	}
	fin<int> R[15][K+1];
	for(int i = 0; i < 15; i++) for(int k = 0; k <= K; k++) R[i][k] = fin(N, 0);
	for(int l = N-1; l >= 0; l--) {
		int cur_val[K+1];
		for(int k = 0; k <= K; k++) {
			R[0][k].put(l, min(N-1, l+A[l]+k));
			cur_val[k] = min(N-1, l+A[l]+k);
		}
		for(int i = 1; i < 15; i++) {
			int nxt_val[K+1];
			for(int k = 0; k <= K; k++) {
				nxt_val[k] = 0;
				for(int k1 = 0; k1 <= k; k1++) nxt_val[k] = max(nxt_val[k], R[i-1][k-k1].get(cur_val[k1]));
			}
			for(int k = 0; k <= K; k++) {
				R[i][k].put(l, nxt_val[k]);
				cur_val[k] = nxt_val[k];
			}
		}
		if(N < 10000) for(auto q : q_by_l[l]) {
			if(q.l == q.r) {
				ans[q.id] = 0;
				continue;
			}
			int ans_lt = 0, ans_ge = N+1;
			int R_lt[K+1];
			for(int k = 0; k <= K; k++) R_lt[k] = l;
			while(ans_ge-ans_lt > 1) {
				int steps = 1, steps_e = 0;
				for(int i = 0; i < 15; i++) if(max(1<<i, ans_ge-ans_lt-(1<<i)) <= max(steps, ans_ge-ans_lt-steps))
					steps = 1<<i, steps_e = i;
				int R_cur[K+1];
				for(int k = 0; k <= K; k++) R_cur[k] = l;
				for(int k = 0; k <= K; k++)
					for(int k1 = 0; k1 <= k; k1++)
						R_cur[k] = max(R_cur[k], R[steps_e][k-k1].get(R_lt[k1]));
				if(R_cur[q.k] >= q.r) ans_ge = ans_lt+steps;
				else {
					ans_lt = ans_lt+steps;
					for(int k = 0; k <= K; k++) R_lt[k] = R_cur[k];
				}
			}
			ans[q.id] = ans_ge;
		}
	}
	for(int q = 0; q < Q; q++) cout << ans[q] << "\n";
}

// look at my code
// my code is amazing
