#include <bits/stdc++.h>
template <typename T>
bool chkmin(T &a, T b) {
  return (b < a) ? a = b, 1 : 0;
}
template <typename T>
bool chkmax(T &a, T b) {
  return (b > a) ? a = b, 1 : 0;
}
long long ksm(long long a, long long b) {
  if (b == 0) return 1;
  long long ns = ksm(a, b >> 1);
  ns = ns * ns % 998244353;
  if (b & 1) ns = ns * a % 998244353;
  return ns;
}
using namespace std;
int lb[20005];
const int S = 15;
struct th {
  int step;
  int pl;
  th() { step = pl = 0; }
  th(int a, int b) { step = a, pl = b; }
  bool operator<(const th &a) const {
    if (step != a.step) return step < a.step;
    return pl > a.pl;
  }
};
int k[20005];
th cm[20005][31];
int p[20005][2];
int ans[20005];
th min(th a, th b) {
  if (a < b) return a;
  return b;
}
const int K = 31;
struct ST {
  th mn[20005][S];
  th q(int l, int r) {
    if (l > r) return th(1e9, 1e9);
    int g = lb[r - l + 1];
    th cur = min(mn[r - (1 << g) + 1][g], mn[l][g]);
    return cur;
  }
  void pfr(int pl, th u) {
    mn[pl][0] = u;
    for (int j = 1; j < S; j++) {
      if (pl + (1 << j) >= 20005) continue;
      mn[pl][j] = min(mn[pl][j - 1], mn[pl + (1 << (j - 1))][j - 1]);
    }
  }
} h[K];
int a[20005];
void work(int l, int r, vector<int> qr) {
  for (auto v : qr)
    for (int j = 0; j <= k[v]; j++)
      if (cm[v][j].pl + k[v] - j >= p[v][1]) chkmin(ans[v], cm[v][j].step);
  if (l == r) return;
  vector<int> s[2];
  int mid = (l + r) >> 1;
  for (int i = mid; i >= l; i--)
    for (int j = 0; j < K; j++) {
      th cur = th(1e9, 1e9);
      if (i + j > mid) cur = th(0, i + j);
      if (i != mid && j) chkmin(cur, h[j - 1].mn[i + 1][0]);
      int e = i + a[i];
      if (e + j > mid) chkmin(cur, th(1, e + j));
      th f = h[j].q(i + 1, min(mid, e));
      chkmin(cur, th(f.step + 1, f.pl));
      h[j].pfr(i, cur);
    }
  for (auto v : qr) {
    if (p[v][1] > mid) {
      for (int s = k[v]; s >= 0; s--)
        if (cm[v][s].pl <= mid) {
          th mm = th(1e9, 1e9);
          for (int l = 0; l <= s; l++) {
            if (cm[v][s - l].pl > mid) {
              th cf = cm[v][s - l];
              chkmin(mm, th(cf.step, cf.pl + l));
            } else {
              th nx = h[l].q(p[v][0], cm[v][s - l].pl);
              nx.step += cm[v][s - l].step;
              chkmin(mm, nx);
            }
          }
          cm[v][s] = mm;
        }
    }
  }
  for (auto v : qr)
    if (p[v][1] > mid)
      s[1].push_back(v);
    else
      s[0].push_back(v);
  work(l, mid, s[0]);
  work(mid + 1, r, s[1]);
}
int main() {
  for (int i = 0; i < S; i++)
    for (int j = (1 << i); j < (1 << (i + 1)) && j < 20005; j++) lb[j] = i;
  int n, q;
  cin >> n >> q;
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  vector<int> cur;
  for (int i = 1; i <= q; i++) {
    ans[i] = 1e9;
    scanf("%d%d%d", &p[i][0], &p[i][1], &k[i]);
    cur.push_back(i);
    for (int j = 0; j <= k[i]; j++) cm[i][j] = th(1, p[i][0] + a[p[i][0]] + j);
  }
  work(1, n, cur);
  for (int i = 1; i <= q; i++) {
    if (p[i][0] == p[i][1])
      ans[i] = 0;
    else
      chkmax(ans[i], 1);
    printf("%d\n", ans[i]);
  }
  return 0;
}
