import static java.lang.Integer.parseInt;
import static java.lang.Long.parseLong;
import static java.lang.Math.max;
import static java.lang.Math.min;
import static java.lang.System.exit;
import static java.util.Arrays.fill;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class H {

	static void solve() throws Exception {
		int n = scanInt(), q = scanInt(), a[] = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = scanInt();
		}
		final int layers = 15, maxK = 30;
		int jumps[][][][] = new int[layers][maxK + 1][layers][n];
		for (int k = 0; k <= maxK; k++) {
			int jj[][] = jumps[0][k];
			int jjc[] = jj[0];
			for (int i = 0; i < n; i++) {
				jjc[i] = min(i + a[i] + k, n - 1);
			}
			for (int i = 1; i < layers; i++) {
				int jjp[] = jjc;
				jjc = jj[i];
				int d = 1 << (i - 1);
				for (int j = 0; j < n - d; j++) {
					jjc[j] = max(jjp[j], jjp[j + d]);
				}
				for (int j = max(0, n - d); j < n; j++) {
					jjc[j] = jjp[j];
				}
			}
		}
		int ii[] = new int[n];
		for (int i = 0, j = 0; i < n; i++) {
			if (1 << (j + 1) <= i) {
				++j;
			}
			ii[i] = j;
		}
		for (int c = 1; c < layers; c++) {
			for (int k = 0; k <= maxK; k++) {
				int jj[][] = jumps[c][k];
				int jjc[] = jj[0];
				for (int pk = 0; pk <= k; pk++) {
					int jj1[] = jumps[c - 1][pk][0], jj2[][] = jumps[c - 1][k - pk];
					for (int i = 0; i < n; i++) {
						int j = jj1[i], d = ii[j - i];
						jjc[i] = max(jjc[i], max(jj2[d][i], jj2[d][j - (1 << d) + 1]));
					}
				}
				for (int i = 1; i < layers; i++) {
					int jjp[] = jjc;
					jjc = jj[i];
					int d = 1 << (i - 1);
					for (int j = 0; j < n - d; j++) {
						jjc[j] = min(jjp[j], jjp[j + d]);
					}
					for (int j = max(0, n - d); j < n; j++) {
						jjc[j] = jjp[j];
					}
				}
			}
		}
		int dyn[] = new int[maxK + 1], ndyn[] = new int[maxK + 1];
		for (int qq = 0; qq < q; qq++) {
			int l = scanInt() - 1, r = scanInt() - 1, k = scanInt();
			if (l == r) {
				out.println(0);
				continue;
			}
			fill(dyn, 0, k + 1, l);
			int ans = 0;
			c: for (int c = layers - 1; c >= 0; c--) {
				int jjj[][][] = jumps[c];
				for (int ck = 0; ck <= k; ck++) {
					int v = l;
					for (int pk = ck; pk <= k; pk++) {
						int pv = dyn[pk], jj[][] = jjj[pk - ck];
						int d = ii[pv - l];
						v = max(v, max(jj[d][l], jj[d][pv - (1 << d) + 1]));
					}
					if (ck == 0 && v >= r) {
						continue c;
					}
					ndyn[ck] = v;
				}
				int t[] = dyn;
				dyn = ndyn;
				ndyn = t;
				ans += 1 << c;
			}
			out.println(ans + 1);
		}
	}

	static int scanInt() throws IOException {
		return parseInt(scanString());
	}

	static long scanLong() throws IOException {
		return parseLong(scanString());
	}

	static String scanString() throws IOException {
		while (tok == null || !tok.hasMoreTokens()) {
			tok = new StringTokenizer(in.readLine());
		}
		return tok.nextToken();
	}

	static BufferedReader in;
	static PrintWriter out;
	static StringTokenizer tok;

	public static void main(String[] args) {
		try {
			in = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(System.out);
			solve();
			in.close();
			out.close();
		} catch (Throwable e) {
			e.printStackTrace();
			exit(1);
		}
	}
}