#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] = vec;
        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());
    }
};

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

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

int max_towers(int ql, int qr, int d) {
    auto fuck = [&](auto fuck, int l, int r, int max) -> int {
        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;
}