#include <bits/stdc++.h>
using uint = unsigned int;
using cat = long long;
using dbl = long double;
constexpr dbl pi = 3.14159265358979323846;
using namespace std;
template <typename T>
T abs(T x) {
  return (x < 0) ? (-x) : x;
}
cat gcd(cat a, cat b) {
  if (a > b) swap(a, b);
  while (a) {
    cat c = b % a;
    b = a;
    a = c;
  }
  return b;
}
cat pw(cat a, cat e, cat mod) {
  if (e <= 0) return 1;
  cat x = pw(a, e / 2, mod);
  x = x * x % mod;
  return (e & 1) ? x * a % mod : x;
}
template <typename T>
class fin {
  int init_val;
  vector<T> node_val;
  int lastone(int x) { return x & (x ^ (x - 1)); }

 public:
  fin() {}
  fin(int N, T init_val_) : init_val{init_val_} {
    node_val.resize(N + 10, init_val_);
  }
  void put(int pos, T val) {
    for (int i = pos + 1; i < (int)node_val.size(); i += lastone(i))
      node_val[i] = min(node_val[i], val);
  }
  T get(int pos) {
    T ret = init_val;
    for (int i = pos + 1; i > 0; i -= lastone(i)) ret = min(ret, node_val[i]);
    return ret;
  }
};
struct query {
  int l, r, k, id;
};
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cout << fixed << setprecision(12);
  int N, Q;
  cin >> N >> Q;
  constexpr int K = 30;
  vector<int> A(N);
  for (int i = 0; i < N; i++) cin >> A[i];
  vector<int> ans(Q);
  vector<vector<query> > q_by_l(N);
  for (int q = 0; q < Q; q++) {
    int l, r, k;
    cin >> l >> r >> k;
    l--, r--;
    q_by_l[l].push_back({.l = l, .r = r, .k = k, .id = q});
  }
  vector<int> max_dist[15][K + 1];
  for (int k = 0; k <= K; k++) {
    max_dist[0][k].resize(N, 0);
    for (int i = 0; i < N; i++) max_dist[0][k][i] = min(N - 1 - i, A[i] + k);
  }
  for (int i = 1; i < 15; i++)
    for (int k = 0; k <= K; k++) {
      max_dist[i][k].resize(N, 0);
      for (int j = 0; j < N; j++)
        for (int k1 = 0; k1 <= k; k1++)
          for (int m = j; m <= j + max_dist[i - 1][k1][j]; m++)
            max_dist[i][k][j] =
                max(max_dist[i][k][j], m - j + max_dist[i - 1][k - k1][m]);
    }
  for (int l = N - 1; l >= 0; l--)
    for (auto q : q_by_l[l]) {
      if (q.l == q.r) {
        ans[q.id] = 0;
        continue;
      }
      int ans_lt = 0, ans_ge = N + 1;
      int dist_lt[K + 1];
      for (int k = 0; k <= K; k++) dist_lt[k] = 0;
      while (ans_ge - ans_lt > 1) {
        int steps = 1, steps_e = 0;
        for (int i = 0; i < 15; i++)
          if (max(1 << i, ans_ge - ans_lt - (1 << i)) <=
              max(steps, ans_ge - ans_lt - steps))
            steps = 1 << i, steps_e = i;
        int dist[K + 1];
        for (int k = 0; k <= K; k++) dist[k] = 0;
        for (int k1 = 0; k1 < 15; k1++)
          for (int k2 = 0; k2 < 15 - k1; k2++) {
            for (int m = l; m <= l + dist_lt[k1]; m++)
              dist[k1 + k2] =
                  max(dist[k1 + k2], m - l + max_dist[steps_e][k2][m]);
          }
        if (dist[q.k] >= q.r - q.l)
          ans_ge = ans_lt + steps;
        else {
          ans_lt = ans_lt + steps;
          for (int k = 0; k <= K; k++) dist_lt[k] = dist[k];
        }
      }
      ans[q.id] = ans_ge;
    }
  for (int q = 0; q < Q; q++) cout << ans[q] << "\n";
}
