#include "towers.h"

#include <bits/stdc++.h>

using namespace std;

constexpr int inf = 1e9 + 7;

constexpr int R = 1 << 17;

pair<int, int> mn[R * 2], mx[R * 2];

void build() {
    for (int i = R - 1; i > 0; --i) {
        mn[i] = min(mn[i * 2], mn[i * 2 + 1]);
        mx[i] = max(mx[i * 2], mx[i * 2 + 1]);
    }
}

pair<int, int> get_mn(int l, int r) {
    l += R;
    r += R;
    pair<int, int> ans(inf, -1);
    while (l < r) {
        if (l & 1) {
            ans = min(ans, mn[l++]);
        }
        if (r & 1) {
            ans = min(ans, mn[--r]);
        }
        l >>= 1;
        r >>= 1;
    }
    return ans;
}

pair<int, int> get_mx(int l, int r) {
    l += R;
    r += R;
    pair<int, int> ans(-inf, -1);
    while (l < r) {
        if (l & 1) {
            ans = max(ans, mx[l++]);
        }
        if (r & 1) {
            ans = max(ans, mx[--r]);
        }
        l >>= 1;
        r >>= 1;
    }
    return ans;
}

int prv[R], ll[R], rr[R];

void build_tree(int l, int r, int pr) {
    if (l == r) {
        return;
    }
    int m = get_mx(l, r).second;
    prv[m] = pr;
    ll[m] = l;
    rr[m] = r;
    build_tree(l, m, m);
    build_tree(m + 1, r, m);
}

int pr_sum[R];

void init(int n, vector<int> h) {
    for (int i = 0; i < n; ++i) {
        mn[i + R] = mx[i + R] = make_pair(h[i], i);
    }
    build();
    build_tree(0, n, -1);
    for (int i = 0; i < n; ++i) {
        pr_sum[i + 1] = pr_sum[i];
        if (rr[i] == ll[i] + 1) {
            pr_sum[i + 1]++;
        }
    }
}

int max_towers(int l, int r, int d) {
    r++;
    int ans = pr_sum[r] - pr_sum[l];
    if (rr[l] != ll[l] + 1 && rr[l] == l + 1) {
        ans++;
    }
    if (r - 1 != l && rr[r - 1] != ll[r - 1] + 1 && ll[r - 1] == r - 1) {
        ans++;
    }
    return ans;
}