#include <bits/stdc++.h>
using namespace std;
const int M = 20005;
const int N = 31;
int read() {
  int x = 0, f = 1;
  char c;
  while ((c = getchar()) < '0' || c > '9') {
    if (c == '-') f = -1;
  }
  while (c >= '0' && c <= '9') {
    x = (x << 3) + (x << 1) + (c ^ 48);
    c = getchar();
  }
  return x * f;
}
int n, q, a[M], lg[M], f[M][20][N], g[N], tmp[N];
pair<int, int> dp[M][20];
int ask(int l, int r) {
  int k = lg[r - l + 1];
  return max(dp[l][k], dp[r - (1 << k) + 1][k]).second;
}
void init() {
  for (int j = 1; (1 << j) <= n; j++)
    for (int i = 1; i + (1 << j) - 1 <= n; i++)
      dp[i][j] = max(dp[i][j - 1], dp[i + (1 << j - 1)][j - 1]);
  for (int i = 1; i <= n; i++)
    for (int j = 0; j < N; j++) f[i][0][j] = min(n, i + a[i] + j);
  for (int j = 1; (1 << j) <= n; j++)
    for (int i = 1; i <= n; i++)
      for (int k = 0; k < N; k++)
        for (int x = 0; x <= k; x++) {
          int t = ask(i, f[i][j - 1][x]);
          f[i][j][k] = max(f[i][j][k], f[t][j - 1][k - x]);
        }
}
signed main() {
  n = read();
  q = read();
  for (int i = 1; i <= n; i++) {
    a[i] = read();
    dp[i][0] = make_pair(a[i] + i, i);
    if (i > 1) lg[i] = lg[i >> 1] + 1;
  }
  init();
  while (q--) {
    int l = read(), r = read(), k = read(), ans = 0;
    if (l == r) {
      puts("0");
      continue;
    }
    if (l + a[l] + k >= r) {
      puts("1");
      continue;
    }
    for (int i = 0; i <= k; i++) g[i] = l;
    for (int x = 15; x >= 0; x--) {
      if ((1 << x) > n) continue;
      for (int i = 0; i <= k; i++) tmp[i] = g[i];
      for (int i = 0; i <= k; i++) {
        int t = ask(i, g[i]);
        for (int j = 0; i + j <= k; j++)
          tmp[i + j] = max(tmp[i + j], f[t][x][j]);
      }
      int fl = 0;
      for (int i = 0; i <= k; i++)
        if (tmp[i] >= r) fl = 1;
      if (fl) continue;
      for (int i = 0; i <= k; i++) g[i] = tmp[i];
      ans += (1 << x);
    }
    printf("%d\n", ans + 1);
  }
}
