#include "towers.h"
#include <bits/stdc++.h>

using namespace std;

struct BinaryJumps {
    vector<int> nxt, val;
    vector<int> jump, depth, sum;
    int n;

    void build(vector<int> nx, vector<int> value, int type) {
        n = size(nx);
        nxt = std::move(nx), val = std::move(value);
        jump.assign(n, -1), depth.assign(n, 0), sum.assign(n, 0);
        auto init = [&](int i) {
            if (nxt[i] == -1) {
                jump[i] = i;
                depth[i] = 0;
            } else {
                depth[i] = depth[nxt[i]] + 1;
                int a = jump[nxt[i]];
                int b = jump[a];
                if (depth[nxt[i]] - depth[a] == depth[a] - depth[b]) {
                    jump[i] = b;
                    sum[i] = sum[nxt[i]] + sum[a];
                } else {
                    jump[i] = nxt[i];
                }
            }
            sum[i] += val[i];
        };
        if (type == 1) { // R => jump to the right
            for (int i = n - 1; i >= 0; --i) {
                init(i);
            }
        } else { // L => jump to the left
            for (int i = 0; i < n; ++i) {
                init(i);
            }
        }
    }
} L, R;

struct SparseTable {
    vector<vector<pair<int, int>>> mn;

    void init(const vector<int> &a, int p = 1) {
        int n = size(a);
        mn.resize(__lg(n) + 1);
        mn[0].resize(n);
        for (int i = 0; i < n; ++i) {
            mn[0][i] = {a[i] * p, i};
        }
        for (int b = 1; b < size(mn); ++b) {
            mn[b].resize(n - (1 << b) + 1);
            for (int i = 0; i <= n - (1 << b); ++i) {
                mn[b][i] = min(mn[b - 1][i], mn[b - 1][i + (1 << b - 1)]);
            }
        }
    }

    pair<int, int> rangeMin(int l, int r) {
        if (l >= r) {
            return {2e9, -1};
        }
        int b = __lg(r - l);
        return min(mn[b][l], mn[b][r - (1 << b)]);
    }
} stMin, stMax;

int n;
vector<int> h, sumL, sumR, nxtL, nxtR, mx;

int build(int l, int r) {
    if (l >= r) {
        return 0;
    }
    int mid = stMax.rangeMin(l, r).second;
    sumL[mid] = build(l, mid);
    sumR[mid] = build(mid + 1, r);
    mx[mid] = h[mid] - max(stMin.rangeMin(l, mid).first, stMin.rangeMin(mid + 1, r).first);
    return 0; // sumL[mid] + sumR[mid] + (max(stMin.rangeMin(l, mid).first, stMin.rangeMin(mid + 1, r).first))
}

void init(int n, std::vector<int> H) {
    ::n = n;
    ::h = H;
    sumL.assign(n, 0), sumR.assign(n, 0), nxtL.assign(n, -1), nxtR.assign(n, -1), mx.assign(n, 0);
    stMax.init(H, -1);
    stMin.init(H, 1);
    build(0, n);
    sort(mx.begin(), mx.end());
}

int max_towers(int L, int R, int D) {
    return n - (lower_bound(mx.begin(), mx.end(), D) - mx.begin());
}