#include <bits/stdc++.h>
using namespace std;
const int N = 20200;
int n, q;
int a[N];
int L[N];
int tmx[N][15];
int comb(int x, int y) { return a[x] > a[y] ? x : y; }
int getmx(int l, int r) {
  int g = L[r - l + 1];
  return comb(tmx[l][g], tmx[r - (1 << g) + 1][g]);
}
int f[N][31][15];
int kuk[N][15];
int jump(int x, int k) {
  for (int i = 0; i < 15; i++) {
    if (k & (1 << i)) {
      x = kuk[x][i];
    }
  }
  return x;
}
pair<int, int> better(pair<int, int> A, pair<int, int> B) {
  if (A.second > B.second) {
    swap(A, B);
  }
  if (A.first >= B.first) {
    return B;
  }
  if (a[jump(A.second, B.first - A.first)] > a[B.second]) {
    return B;
  }
  return A;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    a[i] += i;
    tmx[i][0] = i;
  }
  for (int i = 2; i < N; i++) {
    L[i] = L[i / 2] + 1;
  }
  for (int i = 1; i < 15; i++) {
    for (int j = 1; j + (1 << i) - 1 <= n; j++) {
      tmx[j][i] = comb(tmx[j][i - 1], tmx[j + (1 << i - 1)][i - 1]);
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= 30; j++) {
      f[i][j][0] = getmx(i, min(n, a[i] + j));
    }
  }
  for (int i = 1; i < 15; i++) {
    for (int j = 1; j <= n; j++) {
      for (int k = 0; k <= 30; k++) {
        for (int k2 = 0; k2 <= k; k2++) {
          f[j][k][i] = comb(f[j][k][i], f[f[j][k2][i - 1]][k - k2][i - 1]);
        }
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < 15; j++) {
      kuk[i][j] = f[i][0][j];
    }
  }
  int inf = 1e9;
  vector<pair<int, int> > dp;
  for (int i = 0; i < q; i++) {
    int l, r, k;
    cin >> l >> r >> k;
    if (l == r) {
      cout << 0 << "\n";
      continue;
    } else if (a[l] + k >= r) {
      cout << 1 << "\n";
      continue;
    }
    dp.resize(k + 1);
    for (int j = 0; j <= k; j++) {
      dp[j] = {inf, 0};
    }
    dp[k] = {0, l};
    for (int j = 14; j >= 0; j--) {
      for (int h = k; h >= 0; h--) {
        if (dp[h].second == 0) {
          continue;
        }
        for (int h2 = 0; h2 <= h; h2++) {
          if (a[f[dp[h].second][h2][j]] < r) {
            dp[h - h2] = better(dp[h - h2], make_pair(dp[h].first + (1 << j),
                                                      f[dp[h].second][h2][j]));
          }
        }
      }
    }
    int res = inf;
    for (int i = 0; i <= k; i++) {
      res = min(res, dp[i].first);
    }
    cout << res + 2 << "\n";
  }
}
