#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> 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);

    for (int i = 0; i < n; i++) {
        if ((i == 0 || input[i - 1] > input[i]) && (i == n - 1 || input[i + 1] > input[i])) {
            shit.push_back(i);
        }
    }
}

int max_towers(int ql, int qr, int d) {
    qr++;
    if (ql + 1 == qr) {
        return 1;
    }

    int it1 = std::lower_bound(shit.begin(), shit.end(), ql) - shit.begin();
    int it2 = std::lower_bound(shit.begin(), shit.end(), qr) - shit.begin();
    int res = it2 - it1;
    res += !std::binary_search(shit.begin(), shit.end(), ql) && input[ql] < input[ql + 1];
    res += !std::binary_search(shit.begin(), shit.end(), qr - 1) && input[qr - 1] < input[qr - 2];
    return res;
}