#include <bits/stdc++.h>
using namespace std;
const int NN = 20007, K = 32;
const int inf = 1e9 + 7;
int dp[NN][K][K];
int tbl[NN];
int state[K], state2[K];
int N = 1;
int tree[4 * NN];
int better(int a, int b) { return a + tbl[a] <= b + tbl[b] ? b : a; }
int range(int x) { return x + tbl[x]; }
int query(int l, int r) {
  l += N;
  r += N;
  int res = better(tree[l], tree[r]);
  while (l / 2 != r / 2) {
    if (l % 2 == 0) res = better(res, tree[l + 1]);
    if (r % 2 == 1) res = better(res, tree[r - 1]);
    l /= 2;
    r /= 2;
  }
  return res;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n, q;
  cin >> n >> q;
  while (N <= n) N *= 2;
  for (int i = 0; i < n; i++) {
    cin >> tbl[i];
    tree[i + N] = i;
  }
  for (int i = n; i < N; i++) tree[i + N] = n - 1;
  for (int i = N - 1; i >= 0; i--) {
    tree[i] =
        tree[2 * i] + tbl[tree[2 * i]] <= tree[2 * i + 1] + tbl[tree[2 * i + 1]]
            ? tree[2 * i + 1]
            : tree[2 * i];
  }
  for (int i = 0; i < n; i++) {
    dp[i][0][0] = query(i, min(n - 1, i + tbl[i]));
    cout << dp[i][0][0] << " ";
    for (int j = 1; j < K; j++) {
      dp[i][0][j] = better(dp[i][0][j - 1], min(n - 1, i + tbl[i] + j));
    }
  }
  cout << "\n";
  for (int j = 1; j < K; j++) {
    for (int i = 0; i < n; i++) {
      for (int k = 0; k < K; k++) {
        dp[i][j][k] = i;
        for (int k1 = 0; k1 <= k; k1++) {
          dp[i][j][k] =
              better(dp[i][j][k], dp[dp[i][j - 1][k1]][j - 1][k - k1]);
        }
      }
    }
  }
  for (int j = 0; j < K; j++) {
    for (int i = 0; i < n; i++) {
      for (int k = 0; k < 10; k++) {
        cout << dp[i][j][k] << " ";
      }
      cout << "\n";
    }
    cout << "\n";
  }
  for (int i = 0; i < q; i++) {
    int l, r, x;
    cin >> l >> r >> x;
    l--, r--;
    if (l == r) {
      cout << 0 << "\n";
      continue;
    }
    if (range(l) + x >= r) {
      cout << 1 << "\n";
      continue;
    }
    for (int i = 0; i <= x; i++) {
      state[i] = l;
    }
    int res = 2;
    for (int d = (1 << 15), d2 = 15; d > 0; d /= 2, d2--) {
      bool skip = false;
      for (int i = 0; skip == false && i <= x; i++) {
        for (int j = 0; j + i <= x; j++) {
          if (range(dp[state[i]][d2][j]) + x - i - j >= r) {
            skip = true;
            break;
          }
        }
      }
      if (skip) continue;
      res += d;
      for (int i = 0; i <= x; i++) {
        state2[i] = state[i];
        for (int j = 0; j <= i; j++) {
          state2[i] = better(state2[i], dp[state[i - j]][d2][j]);
        }
      }
      swap(state, state2);
    }
    cout << res << "\n";
  }
  return 0;
}
