#include <bits/stdc++.h>
using namespace std;
int n, Q;
int a[20005];
pair<int, int> f[30 + 1][15][20005], h[30 + 1][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; ++j)
      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 k = 0; k <= 30; ++k) {
    for (int i = 1; i <= n; ++i)
      h[k][0][i] = make_pair(i, min(i + a[i] + k, n));
    inith(h[k]);
    for (int i = 1; i <= n; ++i) f[k][0][i] = qryh(i, a[i], h[k]);
  }
  for (int j = 1; 1 << j <= n; ++j) {
    for (int k = 0; k <= 30; ++k) {
      memcpy(h[k][0], f[k][j - 1], sizeof(pair<int, int>) * (n + 1));
      inith(h[k]);
    }
    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], qryh(i, f[t][j - 1][i].first, h[k - t]));
  }
  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) d[k] = 0, g[k] = l;
    for (int j = 14; j >= 0; --j)
      for (int k = c; k >= 0; --k) {
        int nwd = d[k], nwg = g[k];
        for (int t = 0; t <= k; ++t) {
          int x = f[k - t][j][g[t]].first, y = f[k - t][j][g[t]].second;
          if (x < r && y > nwg) nwg = y, nwd = d[t] + (1 << j);
        }
      }
    int ans = d[c] + 2;
    printf("%d\n", ans);
  }
  return 0;
}
