#include <bits/stdc++.h>
constexpr int K = 30;
std::vector<int> A;
std::vector<std::array<int, 1 + K>> D;
struct Query {
  int index = 0;
  int l = 0;
  int r = 0;
  int k = 0;
  int answer = 0;
};
static void Solve(std::istream& input, std::ostream& output) {
  int n, q;
  input >> n >> q;
  A.resize(1 + n);
  for (int i = 1; i <= n; i++) {
    input >> A[i];
    A[i] = std::min(A[i] + i, n);
  }
  std::vector<Query> queries;
  queries.resize(q);
  for (int i = 0; i < q; i++) {
    auto& query = queries[i];
    query.index = i;
    input >> query.l >> query.r >> query.k;
  }
  std::sort(queries.begin(), queries.end(), [](const Query& a, const Query& b) {
    int d = a.r - b.r;
    if (d == 0) {
      d = a.index - b.index;
    }
    return d < 0;
  });
  D.resize(1 + n);
  int lmin = 0;
  int rmax = 0;
  int kmax = 0;
  for (int qi = 0; qi < q; qi++) {
    auto& query = queries[qi];
    const int l = query.l;
    const int r = query.r;
    const int k = query.k;
    if (r != rmax) {
      lmin = l;
      rmax = r;
      kmax = k;
      for (int i = qi + 1; i < q; i++) {
        auto& temp = queries[i];
        if (temp.r != r) break;
        lmin = std::min(lmin, temp.l);
        kmax = std::max(kmax, temp.k);
      }
      for (int z = kmax; z >= 0; z--) {
        D[rmax][z] = 0;
      }
      for (int i = rmax - 1; i >= lmin; i--) {
        int a = A[i];
        {
          int d = std::numeric_limits<int>::max();
          for (int j = i + 1; j <= std::min(rmax, a); j++) {
            d = std::min(d, D[j][kmax] + 1);
          }
          D[i][kmax] = d;
        }
        for (int z = kmax - 1; z >= 0; z--) {
          int d = D[i][z + 1];
          for (int j = i + 1; j <= std::min(r, a + (kmax - z)); j++) {
            d = std::min(d, D[j][z] + 1);
          }
          D[i][z] = d;
        }
      }
    }
    int d = std::numeric_limits<int>::max();
    for (int z = 0; z <= query.k; z++) {
      d = std::min(d, D[query.l][z]);
    }
    query.answer = d;
  }
  std::sort(queries.begin(), queries.end(), [](const Query& a, const Query& b) {
    int d = a.index - b.index;
    return d < 0;
  });
  for (auto& query : queries) {
    output << query.answer << std::endl;
  }
}
int main() {
  std::ios::sync_with_stdio(false);
  Solve(std::cin, std::cout);
  return 0;
}
