#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 1e5 + 5;

int a[maxn], n, sz;
int stk[maxn], tp;
int L[maxn], R[maxn], d[maxn], b[maxn];
int nxt[18][maxn], pre[18][maxn];

struct ST
{
    int mi[18], lg[maxn];
    int f[18][maxn];

    void build()
    {
        for (int i = 0; i <= 17; i++) mi[i] = 1 << i;
        for (int i = 1, k = 0; i <= n; i++)
        {
            lg[i] = k; if (i == (1 << (k + 1))) lg[i] = ++k;
            f[0][i] = a[i];
        }
        for (int j = 1; j <= 17; j++)
            for (int i = 1; i + mi[j] - 1 <= n; i++)
                f[j][i] = max(f[j - 1][i], f[j - 1][i + mi[j - 1]]);
    }

    int query(int l, int r)
    {
        int k = lg[r - l + 1];
        return max(f[k][l], f[k][r - mi[k] + 1]);
    }
}st;

int rt[maxn], sum[maxn * 20], ls[maxn * 20], rs[maxn * 20], cnt;
void build(int &k, int l, int r)
{
    k = ++cnt;
    if (l == r) return;
    int mid = (l + r) >> 1; build(ls[k], l, mid); build(rs[k], mid + 1, r);
}
void update(int &k, int p, int l, int r, int x)
{
    k = ++cnt;
    sum[k] = sum[p] + 1, ls[k] = ls[p], rs[k] = rs[p];
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (x <= mid) update(ls[k], ls[p], l, mid, x);
    else update(rs[k], rs[p], mid + 1, r, x);
    sum[k] = sum[ls[k]] + sum[rs[k]];
}
int find(int a, int b, int l, int r, int x)
{
    if (l == r) return sum[b] - sum[a];
    int mid = (l + r) >> 1;
    if (x > mid) return find(rs[a], rs[b], mid + 1, r, x);
    else return find(ls[a], ls[b], l, mid, x) + sum[rs[b]] - sum[rs[a]];
}

void init(int N, vector<int> H)
{
    n = N;
    for (int i = 1; i <= N; i++) a[i] = H[i - 1]; st.build();

    tp = 0;
    for (int i = 1; i <= N; i++)
    {
        while (tp && a[stk[tp]] > a[i]) tp--;
        L[i] = tp ? stk[tp] + 1 : 1;
        stk[++tp] = i;
    }

    tp = 0;
    for (int i = N; i; i--)
    {
        while (tp && a[stk[tp]] > a[i]) tp--;
        R[i] = tp ? stk[tp] - 1 : n;
        d[i] = min(st.query(L[i], i), st.query(i, R[i])) - a[i], b[i] = d[i];
        stk[++tp] = i;
    }
    sort(b + 1, b + N + 1); sz = unique(b + 1, b + N + 1) - b - 1;
    for (int i = 1; i <= N; i++) d[i] = lower_bound(b + 1, b + sz + 1, d[i]) - b;

    build(rt[0], 1, sz);
    for (int i = 1; i <= N; i++) update(rt[i], rt[i - 1], 1, sz, d[i]);

    for (int i = 1; i <= N; i++) nxt[0][i] = R[i] + 1; nxt[0][N + 1] = N + 1;
    for (int j = 1; j <= 17; j++)
        for (int i = 1; i <= N + 1; i++) nxt[j][i] = nxt[j - 1][nxt[j - 1][i]];
    for (int i = 1; i <= N; i++) pre[0][i] = L[i] - 1;
    for (int j = 1; j <= 17; j++)
        for (int i = 1; i <= N; i++) pre[j][i] = pre[j - 1][pre[j - 1][i]];
}

int max_towers(int l, int r, int D)
{
    l++, r++;
    int ans = find(rt[l - 1], rt[r], 1, n, lower_bound(b + 1, b + sz + 1, D) - b);
    int x = l;
    for (int i = 17; ~i; i--)
        if (nxt[i][x] <= n && L[nxt[i][x]] < l) x = nxt[i][x];
    if (st.query(x, R[x]) - a[x] >= D) ans++;
    x = r;
    for (int i = 17; ~i; i--)
        if (pre[i][x] && R[pre[i][x]] > r) x = pre[i][x];
    if (st.query(L[x], x) - a[x] >= D) ans++;
    return max(1, ans);
}

// vector<int> p;

// int main()
// {
//     int nn, q;
//     cin >> nn >> q; p.resize(nn);
//     for (int i = 0; i < nn; i++) cin >> p[i];
//     init(nn, p);
//     while (q--)
//     {
//         int l, r, d;
//         cin >> l >> r >> d;
//         cout << max_towers(l, r, d) << "\n";
//     }
//     return 0;
// }