#include <bits/stdc++.h>

#include "towers.h"

using namespace std;

#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

const ll inf = 1e18;
mt19937 rnd(234);

struct SGT_mn {
    int n;
    vector<pair<ll, int>> t;

    void build(vector<ll> &a) {
        n = 1;
        while (n < (int)a.size()) {
            n *= 2;
        }
        t.assign(n + n, {0, 0});
        for (int i = 0; i < (int)a.size(); i += 1) {
            t[i + n] = make_pair(a[i], i);
        }
        for (int i = n - 1; i >= 1; i -= 1) {
            t[i] = min(t[i + i], t[i + i + 1]);
        }
    }

    pair<ll, int> get(int l, int r) {
        l += n;
        r += n + 1;
        pair<ll, int> rs = {inf, -1};
        while (l < r) {
            if (l & 1) {
                rs = min(rs, t[l]);
                l += 1;
            }
            if (r & 1) {
                r -= 1;
                rs = min(rs, t[r]);
            }
            l /= 2;
            r /= 2;
        }
        return rs;
    }
};

struct SGT_bebra {
    int n;
    vector<vector<ll>> t;

    void build(vector<vector<ll>> &a) {
        n = 1;
        while (n < (int)a.size()) {
            n *= 2;
        }
        t.assign(n + n, {0, 0});
        for (int i = 0; i < (int)a.size(); i += 1) {
            t[i + n] = a[i];
        }
        for (int i = n - 1; i >= 1; i -= 1) {
            t[i].resize((int)t[i + i].size() + (int)t[i + i + 1].size());
            merge(all(t[i + i]), all(t[i + i + 1]), t[i].begin());
        }
    }

    int get(int l, int r, ll x) {
        l += n;
        r += n + 1;
        int rs = 0;
        while (l < r) {
            if (l & 1) {
                rs += lower_bound(all(t[l]), x) - t[l].begin();
                l += 1;
            }
            if (r & 1) {
                r -= 1;
                rs += lower_bound(all(t[r]), x) - t[r].begin();
            }
            l /= 2;
            r /= 2;
        }
        return rs;
    }
};

int n;
vector<ll> a, na;
SGT_mn sgt_mn, sgt_mx;
vector<int> nxt_smlr, prvs_smlr;
vector<ll> bbr;
vector<ll> bbr_srtd;
SGT_bebra sgtl, sgtr;
vector<vector<ll>> dl, dr;
ll super_d;
vector<ll> psms;

void build_super_d(ll d) {
    super_d = d;
    dl.assign(n, vector<ll>());
    dr.assign(n, vector<ll>());
    psms.assign(n + 1, 0);
    for (int i = 0; i < n; i += 1) {
        ll lval = inf;
        ll rval = inf;
        if (prvs_smlr[i] != -1) {
            lval = -sgt_mx.get(prvs_smlr[i] + 1, i - 1).first;
        }
        if (nxt_smlr[i] != n) {
            rval = -sgt_mx.get(i + 1, nxt_smlr[i] - 1).first;
        }
        ll lx = lval - a[i];
        ll rx = rval - a[i];
        if (lx >= d && rx >= d) {
            psms[i] += 1;
        } else if (lx >= d) {
            dr[i].push_back(-nxt_smlr[i]);
        } else if (rx >= d) {
            dl[i].push_back(prvs_smlr[i]);
        }
    }
    for (int i = 1; i <= n; i += 1) {
        psms[i] += psms[i - 1];
    }
    sgtl.build(dl);
    sgtr.build(dr);
}

ll get_super_d(int l, int r) {
    int rs = psms[r + 1] - psms[l];
    rs += sgtl.get(l, r, l);
    rs += sgtr.get(l, r, -r);
    int i = sgt_mn.get(l, r).second;
    ll lval = inf;
    ll rval = inf;
    if (prvs_smlr[i] != -1) {
        lval = -sgt_mx.get(prvs_smlr[i] + 1, i - 1).first;
    }
    if (nxt_smlr[i] != n) {
        rval = -sgt_mx.get(i + 1, nxt_smlr[i] - 1).first;
    }
    ll lx = lval - a[i];
    ll rx = rval - a[i];
    if (lx < super_d && rx < super_d) {
        rs += 1;
    }
    return rs;
}

void init(int N, vector<int> H) {
    n = N;
    a.resize(n);
    na.resize(n);
    for (int i = 0; i < n; i += 1) {
        a[i] = H[i];
        na[i] = -H[i];
    }
    sgt_mn.build(a);
    sgt_mx.build(na);
    nxt_smlr.resize(n);
    prvs_smlr.resize(n);
    vector<pair<ll, int>> stck = {make_pair(-inf, -1)};
    for (int i = 0; i < n; i += 1) {
        while (stck.back().first > a[i]) {
            stck.pop_back();
        }
        prvs_smlr[i] = stck.back().second;
        stck.push_back(make_pair(a[i], i));
    }
    stck = {make_pair(-inf, n)};
    for (int i = n - 1; i >= 0; i -= 1) {
        while (stck.back().first >= a[i]) {
            stck.pop_back();
        }
        nxt_smlr[i] = stck.back().second;
        stck.push_back(make_pair(a[i], i));
    }
    bbr.resize(n);
    for (int i = 0; i < n; i += 1) {
        ll lval = inf;
        ll rval = inf;
        if (prvs_smlr[i] != -1) {
            lval = -sgt_mx.get(prvs_smlr[i] + 1, i - 1).first;
        }
        if (nxt_smlr[i] != n) {
            rval = -sgt_mx.get(i + 1, nxt_smlr[i] - 1).first;
        }
        bbr[i] = min(lval, rval) - a[i];
    }
    bbr_srtd = bbr;
    sort(all(bbr_srtd));
    super_d = -1;
}

int solve_rec(int l, int r, ll lval, ll rval, ll lmx, ll rmx, ll d) {
    if (l > r) {
        return 0;
    }
    int mni = sgt_mn.get(l, r).second;
    ll mn = a[mni];
    ll mxl = -sgt_mx.get(l, mni - 1).first;
    ll mxr = -sgt_mx.get(mni + 1, r).first;
    mxl = max(mxl, lmx);
    mxr = max(mxr, rmx);
    if (max(mn, lval) + d > mxl && max(mn, rval) + d > mxr) {
        return 0;
    }
    if (max(mn, lval) + d <= mxl && max(mn, rval) + d <= mxr) {
        return 1 + solve_rec(l, mni - 1, lval, mn, lmx, -inf, d) + solve_rec(mni + 1, r, mn, rval, -inf, rmx, d);
    }
    if (max(mn, lval) + d <= mxl) {
        return solve_rec(l, mni - 1, lval, rval, lmx, mxr, d);
    }
    return solve_rec(mni + 1, r, lval, rval, mxl, rmx, d);
}

int max_towers(int L, int R, int D) {
    if (super_d == -1) {
        build_super_d(D);
    }
    if (D == super_d) {
        int rs = get_super_d(L, R);
        return rs;
    }
    if (L == 0 && R == n - 1) {
        int rs = n - (lower_bound(all(bbr_srtd), D) - bbr_srtd.begin());
        return rs;
    }
    int rs = solve_rec(L, R, -inf, -inf, inf, inf, D);
    return rs;
}