#include <bits/stdc++.h>
template <typename T, int NDIMS>
struct tensor_view {
  static_assert(NDIMS >= 0, "NDIMS must be nonnegative");

 protected:
  std::array<int, NDIMS> shape;
  std::array<int, NDIMS> strides;
  T* data;
  tensor_view(std::array<int, NDIMS> shape_, std::array<int, NDIMS> strides_,
              T* data_)
      : shape(shape_), strides(strides_), data(data_) {}

 public:
  tensor_view() : shape{0}, strides{0}, data(nullptr) {}

 protected:
  int flatten_index(std::array<int, NDIMS> idx) const {
    int res = 0;
    for (int i = 0; i < NDIMS; i++) {
      res += idx[i] * strides[i];
    }
    return res;
  }
  int flatten_index_checked(std::array<int, NDIMS> idx) const {
    int res = 0;
    for (int i = 0; i < NDIMS; i++) {
      assert(0 <= idx[i] && idx[i] < shape[i]);
      res += idx[i] * strides[i];
    }
    return res;
  }

 public:
  T& operator[](std::array<int, NDIMS> idx) const {
    return data[flatten_index(idx)];
  }
  T& at(std::array<int, NDIMS> idx) const {
    return data[flatten_index_checked(idx)];
  }
  template <int D = NDIMS>
  typename std::enable_if<(0 < D), tensor_view<T, NDIMS - 1>>::type operator[](
      int idx) const {
    std::array<int, NDIMS - 1> nshape;
    std::copy(shape.begin() + 1, shape.end(), nshape.begin());
    std::array<int, NDIMS - 1> nstrides;
    std::copy(strides.begin() + 1, strides.end(), nstrides.begin());
    T* ndata = data + (strides[0] * idx);
    return tensor_view<T, NDIMS - 1>(nshape, nstrides, ndata);
  }
  template <int D = NDIMS>
  typename std::enable_if<(0 < D), tensor_view<T, NDIMS - 1>>::type at(
      int idx) const {
    assert(0 <= idx && idx < shape[0]);
    return operator[](idx);
  }
  template <int D = NDIMS>
  typename std::enable_if<(0 == D), T&>::type operator*() const {
    return *data;
  }
  template <typename U, int D>
  friend struct tensor_view;
  template <typename U, int D>
  friend struct tensor;
};
template <typename T, int NDIMS>
struct tensor {
  static_assert(NDIMS >= 0, "NDIMS must be nonnegative");

 protected:
  std::array<int, NDIMS> shape;
  std::array<int, NDIMS> strides;
  int len;
  T* data;

 public:
  tensor() : shape{0}, strides{0}, len(0), data(nullptr) {}
  explicit tensor(std::array<int, NDIMS> shape_, const T& t = T()) {
    shape = shape_;
    strides[NDIMS - 1] = 1;
    for (int i = NDIMS - 1; i > 0; i--) {
      strides[i - 1] = strides[i] * shape[i];
    }
    len = strides[0] * shape[0];
    data = new T[len];
    std::fill(data, data + len, t);
  }
  tensor(const tensor& o)
      : shape(o.shape), strides(o.strides), len(o.len), data(new T[len]) {
    for (int i = 0; i < len; i++) {
      data[i] = o.data[i];
    }
  }
  tensor& operator=(tensor&& o) noexcept {
    using std::swap;
    swap(shape, o.shape);
    swap(strides, o.strides);
    swap(len, o.len);
    swap(data, o.data);
    return *this;
  }
  tensor(tensor&& o) : tensor() { *this = std::move(o); }
  tensor& operator=(const tensor& o) { return *this = tensor(o); }
  ~tensor() { delete[] data; }
  using view_t = tensor_view<T, NDIMS>;
  view_t view() { return tensor_view<T, NDIMS>(shape, strides, data); }
  operator view_t() { return view(); }
  using const_view_t = tensor_view<const T, NDIMS>;
  const_view_t view() const {
    return tensor_view<const T, NDIMS>(shape, strides, data);
  }
  operator const_view_t() const { return view(); }
  T& operator[](std::array<int, NDIMS> idx) { return view()[idx]; }
  T& at(std::array<int, NDIMS> idx) { return view().at(idx); }
  const T& operator[](std::array<int, NDIMS> idx) const { return view()[idx]; }
  const T& at(std::array<int, NDIMS> idx) const { return view().at(idx); }
  template <int D = NDIMS>
  typename std::enable_if<(0 < D), tensor_view<T, NDIMS - 1>>::type operator[](
      int idx) {
    return view()[idx];
  }
  template <int D = NDIMS>
  typename std::enable_if<(0 < D), tensor_view<T, NDIMS - 1>>::type at(
      int idx) {
    return view().at(idx);
  }
  template <int D = NDIMS>
  typename std::enable_if<(0 < D), tensor_view<const T, NDIMS - 1>>::type
  operator[](int idx) const {
    return view()[idx];
  }
  template <int D = NDIMS>
  typename std::enable_if<(0 < D), tensor_view<const T, NDIMS - 1>>::type at(
      int idx) const {
    return view().at(idx);
  }
  template <int D = NDIMS>
  typename std::enable_if<(0 == D), T&>::type operator*() {
    return *view();
  }
  template <int D = NDIMS>
  typename std::enable_if<(0 == D), const T&>::type operator*() const {
    return *view();
  }
};
template <typename T>
void setmax(T& a, T b) {
  if (b > a) a = b;
}
int main() {
  using namespace std;
  ios_base::sync_with_stdio(false), cin.tie(nullptr);
  int N, Q;
  cin >> N >> Q;
  vector<int> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i];
    A[i] = min(i + A[i], N - 1);
  }
  const int MAXK = 30;
  int S = 0;
  while ((1 << S) <= N) S++;
  tensor<pair<int, int>, 3> dp({S + 1, N, MAXK + 1});
  {
    vector<pair<int, int>> stk;
    stk.reserve(N);
    for (int i = N - 1; i >= 0; i--) {
      while (!stk.empty() && A[i] > stk.back().first) stk.pop_back();
      stk.push_back({A[i], i});
      int lo = -1, hi = int(stk.size()) - 1;
      while (hi - lo > 1) {
        int md = (lo + hi) / 2;
        if (stk[md].second <= A[i])
          hi = md;
        else
          lo = md;
      }
      pair<int, int> cur = stk[hi];
      dp[{0, i, 0}] = cur;
      for (int k = 1; k <= MAXK; k++) {
        if (A[i] + k < N) cur = max(cur, {A[A[i] + k], A[i] + k});
        dp[{0, i, k}] = cur;
      }
    }
  }
  for (int s = 1; s <= S; s++) {
    for (int i = 0; i < N; i++) {
      for (int k1 = 0; k1 <= MAXK; k1++) {
        int j = dp[{s - 1, i, k1}].second;
        for (int k2 = 0; k1 + k2 <= MAXK; k2++) {
          setmax(dp[{s, i, k1 + k2}], dp[{s - 1, j, k2}]);
        }
      }
    }
  }
  while (Q--) {
    int L, R, K;
    cin >> L >> R >> K;
    L--, R--;
    cout << [&]() -> int {
      if (L == R) return 0;
      if (A[L] + K >= R) return 1;
      int resp = 1;
      vector<pair<int, int>> cur(K + 1, {A[L], L});
      vector<pair<int, int>> nxt(K + 1);
      auto is_done = [&](const vector<pair<int, int>>& v) {
        for (int k = 0; k <= K; k++) {
          if (v[k].first + (K - k) >= R) return true;
        }
        return false;
      };
      int s = 0;
      while (true) {
        for (int k = 0; k <= K; k++) {
          nxt[k] = dp[{s, L, k}];
        }
        if (is_done(nxt)) {
          break;
        } else {
          s++;
          std::swap(cur, nxt);
        }
      }
      while (s) {
        s--;
        std::copy(cur.begin(), cur.end(), nxt.begin());
        for (int k = 0; k <= K; k++) {
          for (int l = 0; l <= K - k; l++) {
            setmax(nxt[l + k], dp[{s, cur[k].second, l}]);
          }
        }
        if (is_done(nxt)) {
        } else {
          resp += 1 << s;
          std::swap(cur, nxt);
        }
      }
      resp++;
      return resp;
    }() << '\n';
  }
  return 0;
}
