#include <bits/stdc++.h>
using namespace std;
const int maxn = 22222, mod = 998244353, INF = 1e9;
inline long long read() {
  char ch = getchar();
  long long x = 0, f = 0;
  while (ch < '0' || ch > '9') f |= ch == '-', ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  return f ? -x : x;
}
inline int qmo(int x) { return x + (x >> 31 ? mod : 0); }
int n, q, a[maxn], to2[15][maxn][33], lt[maxn];
pair<int, int> to1[15][maxn][33], mx[15][maxn];
struct wtf {
  int a, b, c;
  bool operator<(const wtf &w) const {
    if (a != w.a) return a < w.a;
    if (b != w.b) return b > w.b;
    return c > w.c;
  }
};
wtf f[33], g[33];
inline pair<int, int> query(int l, int r) {
  int k = lt[r - l + 1];
  return max(mx[k][l], mx[k][r - (1 << k) + 1]);
}
int main() {
  n = read();
  q = read();
  for (int i = (1); i <= (n); i++) a[i] = read();
  for (int i = (2); i <= (n); i++) lt[i] = lt[i >> 1] + 1;
  for (int i = (1); i <= (n); i++) mx[0][i] = make_pair(min(n, i + a[i]), i);
  for (int i = (1); i <= (lt[n]); i++)
    for (int j = (1); j <= (n - (1 << i) + 1); j++)
      mx[i][j] = max(mx[i - 1][j], mx[i - 1][j + (1 << (i - 1))]);
  for (int i = (1); i <= (n); i++)
    for (int j = (0); j <= (30); j++)
      to1[0][i][j] = query(i, min(n, i + a[i] + j));
  for (int i = (1); i <= (14); i++)
    for (int j = (1); j <= (n); j++) {
      for (int k = (0); k <= (30); k++)
        for (int l = (0); l <= (k); l++)
          to1[i][j][k] =
              max(to1[i][j][k], to1[i - 1][to1[i - 1][j][l].first][k - l]);
      for (int k = (1); k <= (30); k++)
        to1[i][j][k] = max(to1[i][j][k], to1[i][j][k - 1]);
    }
  for (int i = (1); i <= (n); i++)
    for (int j = (0); j <= (30); j++) to2[0][i][j] = min(n, i + a[i] + j);
  for (int i = (1); i <= (14); i++)
    for (int j = (1); j <= (n); j++) {
      for (int k = (0); k <= (30); k++)
        for (int l = (0); l <= (k); l++)
          to2[i][j][k] =
              max(to2[i][j][k], to2[i - 1][to1[i - 1][j][l].first][k - l]);
      for (int k = (1); k <= (30); k++)
        to2[i][j][k] = max(to2[i][j][k], to2[i][j][k - 1]);
    }
  while (q--) {
    int l = read(), r = read(), m = read();
    if (l == r) {
      puts("0");
      continue;
    }
    if (l + a[l] + m >= r) {
      puts("1");
      continue;
    }
    for (int i = (0); i <= (m); i++) f[i] = (wtf){0, min(n, l + a[l]), l};
    for (int i = (14); i >= (0); i--) {
      for (int j = (0); j <= (m); j++) g[j] = (wtf){INF, 0, 0};
      for (int j = (0); j <= (m); j++)
        for (int k = (0); k <= (m - j); k++) {
          int at = f[j].c;
          if (to2[i][at][k] >= r)
            g[j] = min(g[j], f[j]);
          else {
            wtf w = f[j];
            w.a += 1 << i;
            w.b = to1[i][at][k].first;
            w.c = to1[i][at][k].second;
            g[j + k] = min(g[j + k], w);
          }
        }
      for (int j = (1); j <= (m); j++) g[j] = min(g[j], g[j - 1]);
      for (int j = (0); j <= (m); j++) f[j] = g[j];
    }
    int ans = INF;
    for (int i = (0); i <= (m); i++)
      if (f[i].b + m - i >= r) ans = min(ans, f[i].a + 1);
    printf("%d\n", ans);
  }
}
