#include <bits/stdc++.h>
using namespace std;
std::mt19937 rnd(
    (int)std::chrono::steady_clock::now().time_since_epoch().count());
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
const int MAXN = 20000;
const int MAXLG = 16;
const int MAXQ = 20000;
const int MAXKILL = 30;
int n, nq;
int a[MAXN];
int ql[MAXQ], qr[MAXQ], qkill[MAXQ];
int qans[MAXQ];
pair<int, int> jump[MAXN][MAXLG + 1][MAXKILL + 1];
struct RMQ {
  int lg[MAXN + 1];
  int val[MAXN][MAXLG + 1];
  void init() {
    lg[1] = 0;
    for (int i = (2); i <= (n); ++i) lg[i] = lg[i >> 1] + 1;
    for (int i = (0); i < (n); ++i) val[i][0] = i;
    for (int k = (0); k < (MAXLG); ++k)
      for (int i = (0); i <= (n - (2 << k)); ++i) {
        int x = val[i][k], y = val[i + (1 << k)][k];
        val[i][k + 1] = x + a[x] >= y + a[y] ? x : y;
      }
  }
  int get(int l, int r) {
    int k = lg[r - l + 1];
    int x = val[l][k], y = val[r - (1 << k) + 1][k];
    return x + a[x] >= y + a[y] ? x : y;
  }
};
RMQ rmq;
void solve() {
  rmq.init();
  for (int i = (0); i < (n); ++i)
    for (int k = (0); k <= (MAXLG); ++k)
      for (int x = (0); x <= (MAXKILL); ++x) jump[i][k][x] = make_pair(i, i);
  for (int i = (0); i < (n); ++i)
    for (int x = (0); x <= (MAXKILL); ++x) {
      int upto = min(n - 1, i + a[i] + x);
      jump[i][0][x] = make_pair(upto, rmq.get(i, upto));
    }
  for (int k = (0); k < (MAXLG); ++k)
    for (int i = (0); i < (n); ++i)
      for (int x = (0); x <= (MAXKILL); ++x) {
        int at = jump[i][k][x].second;
        for (int y = (0); y <= (MAXKILL - x); ++y)
          if (jump[at][k][y].first > jump[i][k + 1][x + y].first)
            jump[i][k + 1][x + y] = jump[at][k][y];
      }
  for (int i = (0); i < (nq); ++i) {
    qans[i] = 0;
    if (ql[i] == qr[i]) continue;
    vector<int> best(qkill[i] + 1, ql[i]);
    for (int k = MAXLG; k >= 0; --k) {
      bool ok = false;
      for (int x = (0); x <= (qkill[i]); ++x)
        if (best[x] != -1 && jump[best[x]][k][qkill[i] - x].first >= qr[i])
          ok = true;
      if (ok) continue;
      qans[i] += 1 << k;
      for (int x = qkill[i]; x >= 0; --x) {
        int at = best[x];
        best[x] = -1;
        if (at != -1)
          for (int y = (0); y <= (qkill[i] - x); ++y) {
            pair<int, int> cur = jump[at][k][y];
            if (best[x + y] == -1 || cur.first > a[best[x + y]])
              best[x + y] = cur.second;
          }
      }
    }
    ++qans[i];
  }
}
void run() {
  scanf("%d%d", &n, &nq);
  for (int i = (0); i < (n); ++i) scanf("%d", &a[i]);
  for (int i = (0); i < (nq); ++i)
    scanf("%d%d%d", &ql[i], &qr[i], &qkill[i]), --ql[i], --qr[i];
  solve();
  for (int i = (0); i < (nq); ++i) printf("%d\n", qans[i]);
}
int main() {
  run();
  return 0;
}
