#include "towers.h"

#include <algorithm>
#include <cassert>
#include <functional>
#include <numeric>
#include <vector>

template <typename cmp_t>
struct ST {
    std::vector<std::vector<std::pair<int, int>>> data;

    ST() = default;
    ST(std::vector<int> vec) {
        int lg = std::__lg(vec.size()) + 1;
        data.resize(lg);
        data[0].resize(vec.size());
        for (int i = 0; i < vec.size(); i++) {
            data[0][i] = {vec[i], i};
        }
        for (int k = 1; k < lg; k++) {
            data[k].resize(vec.size() - (1 << k) + 1);
            for (int i = 0; i < data[k].size(); i++) {
                data[k][i] = std::min(data[k - 1][i], data[k - 1][i + (1 << k - 1)], cmp_t());
            }
        }
    }

    auto get_min(int l, int r) {
        int k = std::__lg(r - l);
        return std::min(data[k][l], data[k][r - (1 << k)], cmp_t());
    }
};

int n, q;
ST<std::less<>> st_min;
ST<std::greater<>> st_max;
std::vector<int> input;

std::vector<int> lvs;
std::vector<int> h_lca;
std::vector<int> shit;

void init(int n, std::vector<int> H) {
    q = 0;
    ::n = n;
    input = H;
    st_min = ST<std::less<>>(input);
    st_max = ST<std::greater<>>(input);

    h_lca.assign(n, -1);

    auto fuck = [&](auto fuck, int l, int r) -> std::pair<int, int> {
        if (l >= r) {
            return {int(1e9), (int)1e9};
        }
        if (l + 1 == r) {
            int rs = lvs.size();
            // lvs.push_back(l);
            // return {rs, rs};
            return {input[l], input[l]};
        }
        int id = st_max.get_min(l, r).second;
        auto [p1, p2] = fuck(fuck, l, id);
        auto [p3, p4] = fuck(fuck, id + 1, r);

        int a = std::min(p1, p2);
        int b = std::min(p3, p4);
        shit.push_back(input[id] - std::max(a, b));
        return {a, b};
    };

    fuck(fuck, 0, n);
    // for (int i = 0; i < n - 1; i++) {
    //     if (h_lca[i] != -1) {
    //         shit.push_back(h_lca[i] - std::max(input[lvs[i]], input[lvs[i + 1]]));
    //     }
    // }
    std::sort(shit.begin(), shit.end());
}

int max_towers(int ql, int qr, int d) {
    ::q++;
    qr++;

    // return 0;
    {
        int it = shit.end() - std::lower_bound(shit.begin(), shit.end(), d);
        return it + 1;
    }

    // #ifndef LOCAL
    //     if (q <= 1) {
    //         auto fuck = [&](auto fuck, int l, int r, int max) -> int {
    //             if (l >= r) {
    //                 return 0;
    //             }
    //             int res = st_min.get_min(l, r).first <= max ? 1 : 0;
    //             if (l + 1 < r) {
    //                 int id = st_max.get_min(l, r).second;
    //                 int res2 = 0;
    //                 res2 += fuck(fuck, l, id, input[id] - d);
    //                 res2 += fuck(fuck, id + 1, r, input[id] - d);
    //                 res = std::max(res, res2);
    //             }
    //             return res;
    //         };
    //         int res = fuck(fuck, ql, qr, 1.1e9);
    //         return res;
    //     }
    // #endif

    int it1 = std::lower_bound(lvs.begin(), lvs.end(), ql) - lvs.begin();
    int it2 = std::lower_bound(lvs.begin(), lvs.end(), qr) - lvs.begin();

    int res = 1;
    for (int i = it1; i + 1 < it2; i++) {
        res += std::max(input[lvs[i]], input[lvs[i + 1]]) + d <= h_lca[i];
    }
    return res;
}