#include <bits/stdc++.h>
using namespace std;
int n, Q;
int a[20005];
int f[30 + 1][15][20005];
pair<int, int> h[15][20005];
void inith(pair<int, int> a[][20005]) {
  for (int j = 1; 1 << j <= n; ++j)
    for (int i = 1; i + (1 << j) - 1 <= n; ++i)
      a[j][i] = max(a[j - 1][i], a[j - 1][i + (1 << j - 1)]);
}
int lg[20005];
pair<int, int> qryh(int l, int r, pair<int, int> a[][20005]) {
  int m = lg[r - l + 1];
  return max(a[m][l], a[m][r - (1 << m) + 1]);
}
int g[30 + 1], d[30 + 1];
int main() {
  scanf("%d%d", &n, &Q);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  lg[1] = 0;
  for (int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
  for (int i = 1; i <= n; ++i) h[0][i] = make_pair(min(i + a[i], n), i);
  inith(h);
  for (int k = 0; k <= 30; ++k)
    for (int i = 1; i <= n; ++i) f[k][0][i] = min(i + a[i] + k, n);
  for (int j = 1; j <= 14; ++j)
    for (int k = 0; k <= 30; ++k)
      for (int t = 0; t <= k; ++t)
        for (int i = 1; i <= n; ++i)
          f[k][j][i] = max(f[k][j][i],
                           f[k - t][j - 1][qryh(i, f[t][j - 1][i], h).second]);
  while (Q--) {
    int l, r, c;
    scanf("%d%d%d", &l, &r, &c);
    if (l == r) {
      printf("0\n");
      continue;
    }
    if (l + a[l] + c >= r) {
      printf("1\n");
      continue;
    }
    for (int k = 0; k <= c; ++k) g[k] = l + a[l] + k;
    int ans = 0;
    for (int j = 0; j >= 0; --j) {
      bool bz = 0;
      for (int k = 0; k <= c; ++k) {
        d[k] = g[k];
        for (int t = 0; t <= k; ++t)
          d[k] = max(d[k], f[k - t][j][qryh(l, g[t], h).second]);
        bz |= (d[k] >= r);
      }
      if (bz) continue;
      ans += 1 << j;
      memcpy(g, d, sizeof(int) * (c + 1));
    }
    printf("%d\n", ans + 2);
  }
  return 0;
}
