#include <bits/stdc++.h>
#include "towers.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAXN = 1e5 + 5;
const int LB = 18 + 2;
const int inf = 0x3f3f3f3f;

int lb[MAXN];

namespace SegT {
const int MAXP = MAXN * (LB + 5);
int sum[MAXP], ls[MAXP], rs[MAXP], pcnt = 0;
#define lson(u) ls[u],l,mid
#define rson(u) rs[u],mid+1,r
void insert(int &u, int l, int r, int q) {
    int v = ++pcnt;
    sum[v] = sum[u];
    ls[v] = ls[u];
    rs[v] = rs[u];
    u = v;
    ++sum[u];

    if (l == r)
        return;

    int mid = (l + r) >> 1;
    q <= mid ? insert(lson(u), q) : insert(rson(u), q);
}
int getsum(int u, int l, int r, int ql, int qr) {
    if (u == 0)
        return 0;

    if (ql <= l && r <= qr)
        return sum[u];

    int mid = (l + r) >> 1;

    if (ql <= mid && mid < qr)
        return getsum(lson(u), ql, qr) + getsum(rson(u), ql, qr);
    else
        return ql <= mid ? getsum(lson(u), ql, qr) : getsum(rson(u), ql, qr);
}
int n;
void insert(int &u, int q) {
    insert(u, 1, n, q);
}
int getsum(int u, int ql, int qr) {
    return ql <= qr ? getsum(u, 1, n, ql, qr) : 0;
}
}

int n;
int h[MAXN];

pii stmn[MAXN][LB], stmx[MAXN][LB];
pii getmn(int l, int r) {
    int k = lb[r - l + 1];
    return min(stmn[l][k], stmn[r - (1 << k) + 1][k]);
}
pii getmx(int l, int r) {
    int k = lb[r - l + 1];
    return max(stmx[l][k], stmx[r - (1 << k) + 1][k]);
}

int val[MAXN];
int dsc[MAXN], dcnt = 0, rt[MAXN];

void init(int _n, vector<int> _h) {
    lb[0] = -1;

    for (int i = 1; i < MAXN; ++i)
        lb[i] = lb[i >> 1] + 1;

    n = _n;

    for (int i = 1; i <= n; ++i)
        h[i] = _h[i - 1];

    for (int i = n; i >= 1; --i) {
        stmn[i][0] = stmx[i][0] = {h[i], i};

        for (int j = 1; i + (1 << j) - 1 <= n; ++j) {
            stmn[i][j] = min(stmn[i][j - 1], stmn[i + (1 << (j - 1))][j - 1]);
            stmx[i][j] = max(stmx[i][j - 1], stmx[i + (1 << (j - 1))][j - 1]);
        }
    }

    memset(val, 0x3f, sizeof(val));

    static int sta[MAXN], tp = 0;

    for (int i = 1; i <= n; ++i) {
        while (tp && h[sta[tp]] <= h[i]) {
            int j = sta[tp--];
            val[j] = j == i - 1 ? -1 : min(val[j], h[j] - getmn(j + 1, i - 1).first);
        }

        int j = sta[tp];
        sta[++tp] = i;
        val[i] = j == i - 1 ? -1 : min(val[i], h[i] - getmn(j + 1, i - 1).first);
    }

    while (tp) {
        int i = sta[tp--];
        val[i] = i == n ? -1 : min(val[i], h[i] - getmn(i + 1, n).first);
    }

    for (int i = 1; i <= n; ++i)
        dsc[++dcnt] = val[i];

    sort(dsc + 1, dsc + dcnt + 1);
    dcnt = unique(dsc + 1, dsc + dcnt + 1) - dsc - 1;

    static vector<int> eff[MAXN];

    for (int i = 1; i <= n; ++i) {
        int j = lower_bound(dsc + 1, dsc + dcnt + 1, val[i]) - dsc;
        eff[j].emplace_back(i);
    }

    // for(int i=1; i<=n; ++i)
    // {
    //  printf("val[%d] = %d\n",i,val[i]);
    // }

    SegT :: n = n;

    for (int i = dcnt; i >= 1; --i) {
        rt[i] = rt[i + 1];

        for (int j : eff[i])
            SegT :: insert(rt[i], j);
    }
}

int max_towers(int l, int r, int k) {
    ++l;
    ++r;

    int pos = lower_bound(dsc + 1, dsc + dcnt + 1, k) - dsc;
    int res = SegT :: getsum(rt[pos], l, r);

    auto chkr = [&](int i) -> bool {
        if (i >= r)
            return 0;

        return h[i] - getmn(i + 1, r).first >= k;
    };
    auto chkl = [&](int i) -> bool {
        if (i <= l)
            return 0;

        return h[i] - getmn(l, i - 1).first >= k;
    };

    {
        int vl = l, vr = r;

        while (vl < vr) {
            int vmid = (vl + vr) >> 1;

            if (chkr(getmx(vmid, r).second))
                vl = vmid + 1;
            else
                vr = vmid;
        }

        int i = getmx(vl, r).second;

        if (!chkr(i) && val[i] >= k)
            --res;
    }
    {
        int vl = l, vr = r;

        while (vl < vr) {
            int vmid = (vl + vr + 1) >> 1;

            if (chkl(getmx(l, vmid).second))
                vr = vmid - 1;
            else
                vl = vmid;
        }

        int i = getmx(l, vl).second;

        if (!chkl(i) && val[i] >= k)
            --res;
    }
    {
        int i = getmx(l, r).second;

        if (!chkl(i) && !chkr(i) && val[i] >= k)
            ++res;
    }
    return res + 1;
}