#include <bits/stdc++.h>
const int maxn = 2e4 + 9, mod = 998244353, inf = 0x3f3f3f3f;
int Read() {
  int x(0), f(1);
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = (x << 3ll) + (x << 1ll) + c - '0';
    c = getchar();
  }
  return x * f;
}
void Chkmin(int &x, int y) {
  if (y < x) x = y;
}
void Chkmax(int &x, int y) {
  if (y > x) x = y;
}
int add(int x, int y) { return x += y, x >= mod ? x - mod : x; }
int dec(int x, int y) { return x -= y, x < 0 ? x + mod : x; }
int mul(int x, int y) { return 1ll * x * y % mod; }
int Pow(int base, int b) {
  int ret(1);
  while (b) {
    if (b & 1) ret = mul(ret, base);
    base = mul(base, base);
    b >>= 1;
  }
  return ret;
}
const int Ul = 15, Ku = 30;
namespace Rmq {
int lg[maxn];
std::pair<int, int> mx[maxn][16];
void Init(int *A, int N) {
  for (int i = 1; i <= N; ++i) {
    mx[i][0] = std::pair<int, int>(A[i], i);
  }
  for (int i = 1; i <= 15; ++i) {
    for (int j = 1; j + (1 << i) - 1 <= N; ++j) {
      mx[j][i] = std::max(mx[j][i - 1], mx[j + (1 << i - 1)][i - 1]);
    }
  }
  for (int i = 1; i <= N; ++i) lg[i] = lg[i >> 1] + 1;
}
std::pair<int, int> Query(int l, int r) {
  int len(lg[r - l + 1] - 1);
  return std::max(mx[l][len], mx[r - (1 << len) + 1][len]);
}
}  // namespace Rmq
int n, q;
int a[maxn], f[maxn][31][16];
void Init() {
  n = Read();
  q = Read();
  for (int i = 1; i <= n; ++i) {
    a[i] = Read();
  }
  for (int i = 1; i <= n + 1; ++i) {
    a[i] += i;
  }
  Rmq::Init(a, n + 1);
  for (int j = 0; j <= Ul; ++j) {
    for (int k = 0; k <= Ku; ++k) f[n + 1][k][j] = n + 1;
  }
  for (int i = n; i >= 1; --i) {
    for (int k = 0; k <= Ku; ++k) {
      f[i][k][0] = std::min(a[i] + k, n + 1);
    }
    for (int j = 1; j <= Ul; ++j) {
      for (int k = 0; k <= Ku; ++k) {
        for (int k1 = 0; k1 <= k; ++k1) {
          int x(f[i][k1][j - 1]);
          if (!x) {
            printf("(%d,%d,%d)\n", i, k1, j - 1);
            exit(0);
          }
          std::pair<int, int> tmp(Rmq::Query(i, x));
          Chkmax(f[i][k][j], f[tmp.second][k - k1][j - 1]);
        }
      }
    }
  }
}
void Solve(int l, int r, int K) {
  static int g[31];
  if (l == r) {
    puts("0");
    return;
  }
  Chkmin(K, r - l - 1);
  for (int i = 0; i <= Ku; ++i) {
    g[i] = std::min(n + 1, a[l] + i);
  }
  int ret(1);
  for (int i = 0; i <= K; ++i)
    if (g[i] >= r) {
      puts("1");
      return;
    }
  for (int i = Ul; i >= 0; --i) {
    static int h[31];
    for (int k = 0; k <= Ku; ++k) h[k] = 0;
    for (int k = 0; k <= Ku; ++k) {
      for (int k1 = 0; k1 <= k; ++k1) {
        int x(g[k1]);
        std::pair<int, int> tmp(Rmq::Query(l, x));
        Chkmax(h[k], f[tmp.second][k - k1][i]);
      }
    }
    int flag(0);
    for (int k = 0; k <= K; ++k) flag |= (h[k] >= r);
    if (!flag) {
      for (int k = 0; k <= Ku; ++k) g[k] = h[k];
      ret |= (1 << i);
    }
  }
  printf("%d\n", ret + 1);
}
void Solve() {
  while (q--) {
    int l(Read()), r(Read()), K(Read());
    Solve(l, r, K);
  }
}
int main() {
  Init();
  Solve();
  return 0;
}
