#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  long long 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[20105], st[20105][20], dp[20105][20][35], lg[20105];
int A[35], ans[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;
  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;
  for (int i = n + 1; i <= n + 30; i++) a[i] = 1, st[i][0] = i;
  for (int i = 0; i <= 15; i++)
    if ((1 << i) <= n + 30) lg[(1 << i)] = i;
  for (int i = 3; i <= n + 30; i++)
    if (lg[i] == 0) lg[i] = lg[i - 1];
  for (int i = n + 30; i > 0; i--)
    for (int j = 1; i + (1 << j) - 1 <= n + 30; j++)
      st[i][j] = maxx(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
  for (int i = n; i > 0; i--) {
    for (int k = 0; k <= 30; k++)
      for (int l = 0; l <= k; l++)
        dp[i][0][k] = maxx(
            dp[i][0][k], rmq(i + k + l + 1, i + k + l + a[i + k + l]) + k - l);
    for (int j = 1; j <= 15; j++)
      for (int k = 0; k <= 30; k++)
        for (int l = 0; l <= k; l++)
          dp[i][j][k] =
              maxx(dp[i][j][k], dp[rmq(i, dp[i][j - 1][l])][j - 1][k - l]);
  }
  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;
    }
    for (int i = 0; i <= k; i++) A[i] = l + a[l] + i, ans[i] = 2;
    for (int e = 15; e >= 0; e--) {
      for (int i = k; i >= 0; i--) {
        int B = rmq(l, A[i]), p = 0;
        for (int j = 0; j <= i; j++)
          if (dp[A[j]][e][i - j] > B) B = dp[A[j]][e][i - j], p = j;
        if (p == 0 || B >= r) continue;
        A[i] = B, ans[i] = ans[p] + (1 << e);
      }
    }
    int res = 0x3f3f3f3f;
    for (int i = 0; i <= k; i++) res = min(res, ans[i]);
    printf("%d\n", res);
  }
  return 0;
}
