#include <bits/stdc++.h>
using namespace std;
constexpr int N = 2.1e4, T = 15, K = 31;
int n, m, a[N];
int f[T][K][N], rmq[K][N], lg2[N];
pair<int, int> g[T][K][N];
void work() {
  for (int i = 2; i <= n; ++i) lg2[i] = lg2[i / 2] + 1;
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    for (int k = 0; k < K; ++k) {
      f[0][k][i] = min(n, i + a[i] + k);
      g[0][k][i] = {k, f[0][k][i]};
    }
  }
  for (int t = 1; t < T; ++t) {
    for (int k2 = 0; k2 < K; ++k2) {
      for (int i = 1; i <= n; ++i) rmq[0][i] = i;
      for (int x = 1; x < T; ++x)
        for (int i = 1; i <= n; ++i) {
          int i2 = min(n, i + (1 << (x - 1)));
          int o1 = rmq[x - 1][i];
          int o2 = rmq[x - 1][i2];
          if (f[t - 1][k2][o1] < f[t - 1][k2][o2]) o1 = o2;
          rmq[x][i] = o1;
        }
      for (int k = k2; k < K; ++k) {
        int k1 = k - k2;
        for (int i = n; i; --i) {
          int l = i, r = f[t - 1][k1][i];
          int x = lg2[r - l + 1];
          int best = rmq[x][l];
          int best2 = rmq[x][r - (1 << x) + 1];
          if (f[t - 1][k2][best] < f[t - 1][k2][best2]) best = best2;
          int cur = f[t - 1][k2][best];
          if (cur > f[t][k][i]) {
            f[t][k][i] = cur;
            g[t][k][i] = {k1, best};
          }
        }
      }
    }
  }
  for (int l, r, k, i = 0; i < m; ++i) {
    cin >> l >> r >> k;
    int ans = 0;
    for (int t = T - 2; t >= 0; --t) {
      while (f[t][k][l] < r) {
        ans += 1 << t;
        auto [k1, best] = g[t + 1][k][l];
        if (best <= l) return;
        l = best;
        k -= k1;
      }
    }
    cout << ans + (l < r) << endl;
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  int tc = 1;
  while (tc--) work();
  return 0;
}
