#include "towers.h"
//#include "stub.cpp"
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
struct SegmentTree{
vector<pair<int,int>> tree;
void init(int n, vector<int> a) {
int sz = 1 << __lg(n) + 2;
tree.resize(sz);
build(1, 0, n-1, a);
}
void build(int node, int s, int e, vector<int> &a) {
if (s == e) {
tree[node] = {a[s], s};
return;
}
int mid = s + e >> 1;
build(node*2, s, mid, a);
build(node*2+1, mid+1, e, a);
tree[node] = max(tree[node*2], tree[node*2+1]);
}
pair<int,int> query(int node, int s, int e, int l, int r) {
if (l > e || s > r) return {-inf, -1};
if (l <= s && e <= r) return tree[node];
int mid = s + e >> 1;
return max(query(node*2, s, mid, l, r), query(node*2+1, mid+1, e, l, r));
}
};
/*struct Fenwick{
vector<int> tree;
void init(int n) {
tree.assign(n+1, 0);
}
void upd(int i, int v, int n) {
i ++;
while (i <= n) {
tree[i] += v;
i += i & -i;
}
}
int sum(int i) {
i ++;
int ret = 0;
while
}
}*/
SegmentTree seg;
int Lch[100010], Rch[100010], L[100010], R[100010];
vector<int> H;
int N;
int root;
int S[100010], leaf[100010];
int makeTree(int l, int r) {
if (l > r) return -1;
pair<int,int> ret = seg.query(1, 0, N-1, l, r);
int pv = ret.second;
L[pv] = l; R[pv] = r;
Lch[pv] = makeTree(l, pv-1);
Rch[pv] = makeTree(pv+1, r);
if (Lch[pv] == -1 && Rch[pv] == -1) {
leaf[pv] = 1;
}
return pv;
}
void init(int _N, vector<int> _H) {
N = _N;
H = _H;
seg.init(N, H);
root = makeTree(0, N-1);
S[0] = leaf[0];
for (int i=1; i<N; i++) {
S[i] = S[i-1] + leaf[i];
}
}
int max_towers(int l, int r, int D) {
if (l == r) return 1;
int ans = S[r] - (l ? S[l-1] : 0);
if (!leaf[l] && Rch[l] == -1) ans ++;
if (!leaf[r] && Lch[r] == -1) ans ++;
return ans;
}
