#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), -1};
        }
        if (l + 1 == r) {
            int rs = lvs.size();
            lvs.push_back(l);
            return {rs, rs};
        }
        int id = st_max.get_min(l, r).second;
        auto [p1, p2] = fuck(fuck, l, id);
        auto [p3, p4] = fuck(fuck, id + 1, r);
        if (p2 >= 0 && p3 < n) {
            h_lca[p2] = input[id];
        }
        return {std::min(p1, p3), std::max(p2, p4)};
    };
    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++;

    {
        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;
}