#include <bits/stdc++.h>
using namespace std;
int read() {
  char ch = getchar();
  int w = 1, c = 0;
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') w = -1;
  for (; isdigit(ch); ch = getchar()) c = (c << 3) + (c << 1) + (ch ^ 48);
  return w * c;
}
const int M = 2e4 + 10;
int n, a[M], m;
pair<int, int> d[M];
void add(int x, pair<int, int> y) {
  for (; x <= n; x += (x & -x)) d[x] = max(d[x], y);
}
pair<int, int> qry(int x) {
  pair<int, int> ret = make_pair(0, 0);
  for (; x; x -= (x & -x)) ret = max(ret, d[x]);
  return ret;
}
pair<int, int> f[15][M][33];
int g[15][M][33], b[M], tw[33], ted[33];
pair<int, int> nw[33];
int main() {
  n = read();
  m = read();
  for (int i = 1; i <= n; ++i) a[i] = read(), b[i] = min(a[i] + i, n);
  for (int i = n; i >= 1; --i) {
    for (int j = 0; j <= 30; ++j) g[0][i][j] = min(n, b[i] + j);
    add(i, make_pair(b[i], i));
    f[0][i][0] = qry(b[i]);
    int tmp = f[0][i][0].second;
    for (int j = 1; j <= 30; ++j) {
      f[0][i][j] =
          max(f[0][i][j - 1], make_pair(b[min(tmp + j, n)], min(tmp + j, n)));
    }
  }
  for (int t = 1; t <= 14; ++t) {
    for (int i = 1; i <= n; ++i) {
      for (int j = 0; j <= 30; ++j) {
        for (int jj = 0; jj <= j; ++jj) {
          int ps = f[t - 1][i][jj].second;
          f[t][i][j] = max(f[t][i][j], f[t - 1][ps][j - jj]);
          g[t][i][j] = max(g[t][i][j], g[t - 1][ps][j - jj]);
        }
      }
    }
  }
  for (int T = 1; T <= m; ++T) {
    int l = read(), r = read(), k = read();
    if (l == r) {
      cout << 0 << "\n";
      continue;
    }
    for (int i = 0; i <= k; ++i) nw[i] = make_pair(b[l], l);
    int ans = 1e9, cur = 0;
    for (int i = 14; i >= 0; --i) {
      for (int j = 0; j <= k; ++j) tw[j] = nw[j].second, ted[j] = 0;
      for (int j = 0; j <= k; ++j) {
        for (int jj = 0; jj <= j; ++jj) {
          ted[j] = max(ted[j], g[i][tw[jj]][j - jj]);
        }
      }
      int mx = 0;
      for (int j = 0; j <= k; ++j) mx = max(mx, ted[j]);
      if (mx >= r) {
        ans = min(ans, cur | (1 << i));
      } else {
        for (int j = 0; j <= k; ++j) {
          for (int jj = 0; jj <= j; ++jj) {
            nw[j] = max(nw[j], f[i][tw[jj]][j - jj]);
          }
        }
        cur |= (1 << i);
      }
    }
    cout << ans << "\n";
  }
  return 0;
}
