#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int mo = 1e9 + 7;
const int zero = 500;
const long long jzm = 2333;
const int orG = 3, invG = 332748118;
const double Pi = acos(-1.0);
const double PI = acos(-1.0);
template <typename _T>
_T Fabs(_T x) {
  return x < 0 ? -x : x;
}
template <typename _T>
void read(_T &x) {
  _T f = 1;
  x = 0;
  char s = getchar();
  while (s > '9' || s < '0') {
    if (s == '-') f = -1;
    s = getchar();
  }
  while ('0' <= s && s <= '9') {
    x = (x << 3) + (x << 1) + (s ^ 48);
    s = getchar();
  }
  x *= f;
}
template <typename _T>
void print(_T x) {
  if (x < 0) {
    x = (~x) + 1;
    putchar('-');
  }
  if (x > 9) print(x / 10);
  putchar(x % 10 + '0');
}
int add(int x, int y) { return x + y < mo ? x + y : x + y - mo; }
int n, q, a[20005], st[20005][20], f[20005][35][20], lg[20005], A[35], tmp[35];
int step(int x) { return a[x] + x; }
int Max(int x, int y) { return step(x) > step(y) ? x : y; }
int query(int l, int r) {
  r = min(r, n);
  if (l > r) return 0;
  int k = lg[r - l + 1];
  return Max(st[l][k], st[r - (1 << k) + 1][k]);
}
signed main() {
  read(n);
  read(q);
  lg[1] = 0;
  for (int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
  for (int i = 1; i <= n; i++) read(a[i]);
  for (int i = 1; i <= n; i++) st[i][0] = i;
  for (int i = 1; i <= lg[n]; i++)
    for (int j = 1; j <= n - (1 << i) + 1; j++)
      st[j][i] = Max(st[j][i - 1], st[j + (1 << i - 1)][i - 1]);
  for (int i = 1; i <= n; i++)
    for (int j = 0; j <= lg[n]; j++) f[i][j][0] = i + a[i] + j;
  for (int l = 0; l <= lg[n]; l++)
    for (int i = 1; i <= n; i++)
      for (int j = 0; j <= 30; j++) {
        for (int k = 0; j + k <= 30; k++)
          f[i][j + k][l + 1] =
              max(f[i][j + k][l + 1], f[query(i, f[i][j][l])][k][l]);
        for (int k = 0; j + k <= 30; k++)
          f[i][j + k][l + 1] = max(f[i][j][l + 1] + k, f[i][j + k][l + 1]);
      }
  for (int i = 1; i <= q; i++) {
    int l, r, k, minn = 1;
    read(l);
    read(r);
    read(k);
    if (l == r) {
      puts("0");
      continue;
    }
    if (step(l) + k >= r) {
      puts("1");
      continue;
    }
    for (int j = 0; j <= k; j++) A[j] = step(l) + j;
    for (int j = lg[r - l + 1]; j >= 0; j--) {
      for (int i1 = 0; i1 <= k; i1++) tmp[i1] = A[i1];
      bool flag = 0;
      for (int i1 = 0; i1 <= k; i1++)
        for (int i2 = 0; i1 + i2 <= k; i2++)
          if (f[query(l, A[i1])][i2][j] > tmp[i1 + i2])
            tmp[i1 + i2] = f[query(l, A[i1])][i2][j];
      for (int i1 = 0; i1 <= k; i1++)
        if (tmp[i1] >= r) flag = 1;
      if (flag) continue;
      minn += (1 << j);
      for (int i1 = 0; i1 <= k; i1++) A[i1] = tmp[i1];
    }
    printf("%d\n", minn + 1);
  }
  return 0;
}
