#include <bits/stdc++.h>
const int N = 2e4 + 10, LOG = 15, K = 31;
template <typename T>
inline T max(const T &x, const T &y) {
  return x > y ? x : y;
}
template <typename T>
inline T min(const T &x, const T &y) {
  return x < y ? x : y;
}
int n, q, a[N], lg[N], dp[LOG][K][N], f[LOG][K][N], ans[N], pos[K][N];
struct qustion {
  int l, r, k;
} loveti[N];
int query_max(int k, int l, int r) {
  int d = lg[r - l + 1];
  return max(f[d][k][l], f[d][k][r - (1 << d) + 1]);
}
int main() {
  std::ios::sync_with_stdio(0);
  std::cin.tie(0);
  std::cin >> n >> q;
  for (int i = 2; i < N; ++i) {
    lg[i] = lg[i / 2] + 1;
  }
  for (int i = 1; i <= n; ++i) {
    std::cin >> a[i];
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j < K; ++j) {
      dp[0][j][i] = min(a[i] + i + j, n);
    }
  }
  for (int i = 1; i < LOG; ++i) {
    for (int j = 1; j <= n; ++j) {
      for (int k = 0; k < K; ++k) {
        f[0][k][j] = dp[i - 1][k][j];
      }
    }
    for (int l = 1; l < LOG; ++l) {
      for (int k = 0; k < K; ++k) {
        for (int j = 1; j + (1 << l) - 1 <= n; ++j) {
          f[l][k][j] = max(f[l - 1][k][j], f[l - 1][k][j + (1 << l) / 2]);
        }
      }
    }
    for (int k_1 = 0; k_1 < K; ++k_1) {
      for (int k_2 = 0; k_2 + k_1 < K; ++k_2) {
        for (int j = 1; j <= n; ++j) {
          dp[i][k_1 + k_2][j] =
              max(dp[i][k_1 + k_2][j], query_max(k_2, j, dp[i - 1][k_1][j]));
        }
      }
    }
  }
  for (int i = 1; i <= q; ++i) {
    std::cin >> loveti[i].l >> loveti[i].r >> loveti[i].k;
    if (loveti[i].l == loveti[i].r) {
      ans[i] = -1;
    }
    for (int j = 0; j <= loveti[i].k; ++j) {
      pos[j][i] = loveti[i].l;
    }
  }
  for (int i = LOG - 1; ~i; --i) {
    for (int k = 0; k < K; ++k) {
      for (int j = 1; j <= n; ++j) {
        f[0][k][j] = dp[i][k][j];
      }
    }
    for (int l = 1; l < LOG; ++l) {
      for (int k = 0; k < K; ++k) {
        for (int j = 1; j + (1 << i) - 1 <= n; ++j) {
          f[l][k][j] = max(f[l - 1][k][j], f[l - 1][k][j + (1 << i) / 2]);
        }
      }
    }
    for (int j = 1; j <= q; ++j) {
      if (ans[j] == -1) {
        continue;
      }
      static int np[K];
      memset(np, 0, sizeof np);
      for (int k_1 = 0; k_1 <= loveti[j].k; ++k_1) {
        for (int k_2 = 0; k_2 + k_1 <= loveti[j].k; ++k_2) {
          np[k_1 + k_2] =
              max(np[k_1 + k_2], query_max(k_2, loveti[j].l, pos[k_1][j]));
        }
      }
      if (np[loveti[j].k] < loveti[j].r) {
        ans[j] |= 1 << i;
        for (int k = 0; k <= loveti[j].k; ++k) {
          pos[k][j] = np[k];
        }
      }
    }
  }
  for (int i = 1; i <= q; ++i) {
    std::cout << ans[i] + 1 << '\n';
  }
  return 0;
}
