#include <bits/stdc++.h>
using namespace std;
template <typename T>
bool chkmax(T &x, T y) {
  return x < y ? x = y, 1 : 0;
}
template <typename T>
bool chkmin(T &x, T y) {
  return x > y ? x = y, 1 : 0;
}
int readint() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
struct node {
  int l, r, k, res;
  node(int l = 0, int r = 0, int k = 0, int res = 0)
      : l(l), r(r), k(k), res(res) {}
};
const int K = 30;
int n, q;
int lg2[20005], a[20005];
pair<int, int> d[20005][35], f[20005][35], rmq[35][20005][15];
pair<int, int> getmin(int l, int r, int x) {
  int k = lg2[r - l + 1];
  return min(rmq[x][l][k], rmq[x][r - (1 << k) + 1][k]);
}
void update(int pl, pair<int, int> c, int x, int r) {
  rmq[x][pl][0] = c;
  for (int i = 1; pl + (1 << i) - 1 <= r; i++)
    rmq[x][pl][i] = min(rmq[x][pl][i - 1], rmq[x][pl + (1 << (i - 1))][i - 1]);
}
void solve(int l, int r, vector<node> &now) {
  if (!now.size()) return;
  int mid = (l + r) / 2;
  vector<node> lson(0), rson(0);
  for (int i = mid; i >= l; i--) {
    for (int j = 0; j <= K; j++) {
      if (i + a[i] > mid)
        d[i][j] = make_pair(1, -(i + a[i] + j));
      else {
        d[i][j] = min(getmin(i + 1, i + a[i], j), f[i + a[i]][j]),
        d[i][j].first++;
        if (i + a[i] + j > mid) chkmin(d[i][j], make_pair(1, -(i + a[i] + j)));
      }
      f[i][j] = d[i][j];
      if (j && i < mid) chkmin(f[i][j], f[i + 1][j - 1]);
      update(i, d[i][j], j, mid);
    }
  }
  for (auto s : now) {
    if (s.l >= s.r)
      ;
    else if (s.r <= mid)
      lson.push_back(node(s.l, s.r, s.k, 0));
    else if (s.l > mid)
      rson.push_back(node(s.l, s.r, s.k, 0));
    else {
      for (int j = 0; j <= s.k; j++)
        rson.push_back(node(-d[s.l][j].second, s.r, s.k - j, 0));
    }
  }
  solve(l, mid, lson);
  solve(mid + 1, r, rson);
  int pl = 0, pr = 0;
  for (auto &s : now) {
    if (s.l >= s.r)
      ;
    else if (s.r <= mid)
      s.res += lson[pl++].res;
    else if (s.l > mid)
      s.res += rson[pr++].res;
    else {
      int tmp = n;
      for (int j = 0; j <= s.k; j++)
        chkmin(tmp, rson[pr++].res + d[s.l][j].first);
      s.res += tmp;
    }
  }
}
int main() {
  n = readint();
  q = readint();
  for (int i = 1; i <= n; i++) a[i] = readint();
  for (int i = 2; i <= n; i++) lg2[i] = lg2[i >> 1] + 1;
  vector<node> st(0);
  node tmp;
  for (int i = 1; i <= q; i++) {
    tmp.l = readint(), tmp.r = readint(), tmp.k = readint(), tmp.res = 0;
    st.push_back(tmp);
  }
  solve(1, n, st);
  for (int i = 0; i < q; i++) printf("%d\n", st[i].res);
  return 0;
}
