#include<iostream>
using namespace std;

const int NN = 20007, K = 32;
const int inf = 1e9+7;

int dp[NN][K][K];
int tbl[NN];
int state[K], state2[K];

int N = 1;
int tree[4 * NN];

int better(int a, int b) {
    return a + tbl[a] <= b + tbl[b] ? b : a;
}

int range(int x) {
    return x + tbl[x];
}

int query(int l, int r) {
    l += N;
    r += N;
    int res = better(tree[l], tree[r]);
    while(l / 2 != r / 2) {
        if (l % 2 == 0)
            res = better(res, tree[l + 1]);
        if (r % 2 == 1)
            res = better(res, tree[r - 1]);
        l /= 2;
        r /= 2;
    }
    return res;
}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, q;
    cin >> n >> q;
    while(N <= n)
        N *= 2;
    for (int i = 0; i < n; i++) {
        cin >> tbl[i];
        tree[i + N] = i;
    }

    for (int i = n; i < N; i++)
        tree[i + N] = n - 1;

    for (int i = N - 1; i >= 0; i--) {
        tree[i] = tree[2 * i] + tbl[tree[2 * i]] <= tree[2 * i + 1] + tbl[tree[2 * i + 1]] ? 
                  tree [2 * i + 1] : tree[2 * i];
    }

    for (int i = 0; i < n; i++) {
        dp[i][0][0] = query(i, min(n - 1, i + tbl[i]));
        // cout << dp[i][0][0] << " ";
        for (int j = 1; j < K; j++) {
            dp[i][0][j] = better(dp[i][0][j - 1], min(n - 1, i + tbl[i] + j));
        }
    }
    // cout << "\n";

    for (int j = 1; j < K; j++) {
        for (int i = 0; i < n; i++) {
            for (int k = 0; k < K; k++) {
                dp[i][j][k] = i;
                for (int k1 = 0; k1 <= k; k1++) {
                    dp[i][j][k] = better(dp[i][j][k], dp[dp[i][j - 1][k1]][j - 1][k - k1]);
                }
            }
        }
    }

    // for (int j = 0; j < K; j++) {
    //     for (int i = 0; i < n; i++) {
    //         for (int k = 0; k < 10; k++) {
    //             cout << dp[i][j][k] << " ";
    //         }
    //         cout << "\n";
    //     }
    //     cout << "\n";
    // }

    for (int i = 0; i < q; i++) {
        int l, r, x;
        cin >> l >> r >> x;
        l--, r--;
        if (l == r) {
            cout << 0 << "\n";
            continue;
        }
        if (range(l) + x >= r) {
            cout << 1 << "\n";
            continue;
        }
        for (int i = 0; i <= x; i++) {
            state[i] = l;
        }
        int res = 2;
        for (int d = (1<<15), d2 = 15; d > 0; d /= 2, d2--) {
            bool skip = false;
            for (int i = 0; skip == false && i <= x; i++) {
                for (int j = 0; j + i <= x; j++) {
                    if (range(dp[state[i]][d2][j]) + x - i - j >= r) {
                        skip = true;
                        break;
                    }
                }
            }
            if (skip)
                continue;
            res += d;
            for (int i = 0; i <= x; i++) {
                state2[i] = state[i];
                for (int j = 0; j <= i; j++) {
                    state2[i] = better(state2[i], dp[state[i - j]][d2][j]);
                }
            }
            swap(state, state2);
        }
        cout << res << "\n";
    }

    return 0;
}