#include <iostream>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <vector>
#include <cassert>
using namespace std;

#define LOG(f...) fprintf(stderr, f)

using ll = long long;

const int N = 20017;
const int LOGN = 16;
const int MAXK = 30;

struct RMQ {
  int st[N >> 4][LOGN - 4];
  int pre[N], suf[N];

  void initalize(int *a, int n) {
    for (int i = 0; i < n; ++i)
      pre[i] = (i & 15 ? max(pre[i - 1], a[i]) : pre[i - 1]);
    suf[n - 1] = a[n - 1];
    for (int i = n - 2; i >= 0; --i)
      suf[i] = ((i + 1) & 15 ? max(suf[i + 1], a[i]) : a[i]);
    int bc = n >> 4;
    for (int i = 0; i < bc; ++i)
      st[i][0] = suf[i << 4];
    for (int i = 1, li = __lg(bc); i <= li; ++i)
      for (int j = 0, li = n - (1 << i); j <= li; ++j)
        st[i][j] = max(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
  }

  int block_rmq(int l, int r) {
    if (l > r) return -1;
    int k = __lg(r - l + 1);
    return max(st[k][l], st[k][r - (1 << k) + 1]);
  }
  int range_max(int l, int r) {
    assert((l >> 4) != (r >> 4));
    return max({suf[l], pre[r], block_rmq((l >> 4) + 1, (r >> 4) - 1)});
  }
};

int a[N];
int d[16][31][N];
RMQ dr[16][31];
int nxt[31][N][16];
int n, q, logn;

void prework() {
  for (int k = 0; k <= MAXK; ++k)
    for (int j = 0; j < n; ++j)
      d[0][k][j] = min(n - 1, j + a[j] + k);
  for (int k = 0; k <= MAXK; ++k)
    dr[0][k].initalize(d[0][k], n);
  for (int i = 1; i <= logn; ++i)
    for (int k = 0; k <= MAXK; ++k) {
      for (int j = n - 1; j >= 0; --j) {
        nxt[k][j][0] = d[i - 1][k][j];
        for (int st = 1, li = min(n - j, 16); st < li; ++st)
          nxt[k][j][st] = max(d[i - 1][k][j], nxt[k][j + 1][st - 1]);
      }
      for (int j = 0; j < n; ++j)
        for (int lk = 0; lk <= k; ++lk)
          d[i][k][j] = max(d[i][k][j], d[i - 1][lk][j] - j < 16 ? nxt[k - lk][j][d[i - 1][lk][j] - j] : dr[i - 1][k - lk].range_max(j, d[i - 1][lk][j]));
      dr[i][k].initalize(d[i][k], n);
    }
}

int query(int l, int r, int K) {
  if (l == r) return 0;
  static int pos[MAXK + 1], tmp[MAXK + 1];
  static int nxt[LOGN][MAXK + 1][16];
  fill_n(pos, K + 1, l);
  for (int i = 0; i <= logn; ++i)
    for (int k = 0; k <= K; ++k) {
      nxt[i][k][0] = d[i][k][l];
      for (int j = 1, li = min(n - j, 16); j < li; ++j)
        nxt[i][k][j] = max(nxt[i][k][j - 1], d[i][k][l + j]);
    }
  int res = 0;
  for (int i = logn; i >= 0; --i) {
    fill_n(tmp, K + 1, 0);
    for (int lk = 0; lk <= K; ++lk)
      for (int rk = 0, li = K - lk; rk <= li; ++rk)
        tmp[lk + rk] = max(tmp[lk + rk], pos[lk] - l < 16 ? nxt[i][rk][pos[lk] - l] : dr[i][rk].range_max(l, pos[lk]));
    if (*max_element(tmp, tmp + K + 1) < r) {
      res |= (1 << i);
      copy(tmp, tmp + K + 1, pos);
    }
  }
  return res + 1;
}

int main() {
#ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#endif
  cin >> n >> q;
  logn = __lg(n);
  for (int i = 0; i < n; ++i)
    cin >> a[i];
  prework();
  while (q--) {
    int l, r, k;
    cin >> l >> r >> k;
    --l; --r;
    cout << query(l, r, k) << '\n';
  }
  return 0;
}