#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
const long long N = 2e3 + 10;
const long long LOG = 17;
const long long K = 31;
long long dp[LOG][K][N];
long long lg[N];
long long a[N];
long long sparse[K][LOG][N];
long long get_max(long long l, long long r, long long k) {
  long long t = lg[r - l + 1];
  return max(sparse[k][t][l], sparse[k][t][r - (1 << t) + 1]);
}
long long cur_dp[N][K];
long long ans[N];
long long l[N], r[N], k[N];
long long new_dp[K];
signed main() {
  long long n, q;
  cin >> n >> q;
  lg[1] = 0;
  for (long long i = 2; i < N; i++) {
    lg[i] = lg[i / 2] + 1;
  }
  for (long long i = 0; i < n; i++) {
    cin >> a[i];
  }
  for (long long i = 0; i < n; i++) {
    for (long long j = 0; j < K; j++) {
      dp[0][j][i] = min(i + a[i] + j, n - 1);
    }
  }
  for (long long i = 0; i + 1 < LOG; i++) {
    for (long long x = 0; x < K; x++) {
      for (long long y = 0; y < n; y++) {
        sparse[x][0][y] = dp[i][x][y];
      }
      for (long long z = 0; z + 1 < LOG; z++) {
        for (long long y = 0; y + (1 << (z + 1)) <= n; y++) {
          sparse[x][z + 1][y] =
              max(sparse[x][z][y], sparse[x][z][y + (1 << z)]);
        }
      }
    }
    for (long long k1 = 0; k1 < K; k1++) {
      for (long long k2 = 0; k2 + k1 < K; k2++) {
        for (long long x = 0; x < n; x++) {
          dp[i + 1][k1 + k2][x] =
              max(dp[i + 1][k1 + k2][x], get_max(i, dp[i][k1][x], k2));
        }
      }
    }
  }
  for (long long i = 0; i < q; i++) {
    cin >> l[i] >> r[i] >> k[i];
    l[i]--;
    r[i]--;
    if (l[i] == r[i]) {
      ans[i] = -1;
      continue;
    }
    for (long long z = 0; z <= k[i]; z++) {
      cur_dp[i][z] = l[i];
    }
  }
  for (long long i = LOG - 1; i >= 0; i--) {
    for (long long x = 0; x < K; x++) {
      for (long long y = 0; y < n; y++) {
        sparse[x][0][y] = dp[i][x][y];
      }
      for (long long z = 0; z + 1 < LOG; z++) {
        for (long long y = 0; y + (1 << z) <= n; y++) {
          sparse[x][z + 1][y] =
              max(sparse[x][z][y], sparse[x][z][y + (1 << z)]);
        }
      }
    }
    for (long long id = 0; id < q; id++) {
      if (ans[id] == -1) {
        continue;
      }
      memset(new_dp, 0, sizeof(new_dp));
      for (long long was = 0; was <= k[id]; was++) {
        for (long long will = 0; will + was <= k[id]; will++) {
          new_dp[was + will] =
              max(new_dp[was + will], get_max(l[id], cur_dp[id][was], will));
        }
      }
      if (new_dp[k[id]] < r[id]) {
        ans[id] += (1 << i);
        memcpy(cur_dp[i], new_dp, sizeof(new_dp));
      }
    }
  }
  for (long long i = 0; i < q; i++) {
    cout << ans[i] + 1 << "\n";
  }
  return 0;
}
