#include <bits/stdc++.h>
#include "towers.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
vector<int> h;
struct SegTree {
vector<int> tree;
SegTree(int n) {
tree.assign(4*n, 0);
}
void query(int p, int l, int r, int i, int x) {
if (l > i || r < i) return;
if (l==r && r==i) {
tree[p] = x;
return;
}
int m = (l+r)/2;
query(2*p, l, m, i, x);
query(2*p+1, m+1, r, i, x);
int i1 = tree[2*p];
int i2 = tree[2*p+1];
tree[p] = max(i1, i2);
}
int rmq(int p, int l, int r, int i, int j) {
if (l > j || r < i) return 0;
if (i <= l && r <= j) {
return tree[p];
}
int m = (l+r)/2;
int i1 = rmq(2*p, l, m, i, j);
int i2 = rmq(2*p+1, m+1, r, i, j);
return max(i1, i2);
}
int walkleft(int p, int l, int r, int x) {
if (l==r) return l;
int m = (l+r)/2;
if (tree[2*p+1] >= x) {
return walkleft(2*p+1, m+1, r, x);
}
else {
return walkleft(2*p, l, m, x);
}
}
int walkright(int p, int l, int r, int x) {
if (l==r) return l;
int m = (l+r)/2;
if (tree[2*p] >= x) {
return walkright(2*p, l, m, x);
}
else {
return walkright(2*p+1, m+1, r, x);
}
}
};
void init(int N, vector<int> H) {
h = H;
}
bool cmp(int a, int b) {
return h[a] < h[b];
}
int max_towers(int l, int r, int d) {
int n = h.size();
vector<int> L(n, 0), R(n, n-1);
SegTree mx(n);
for (int i=0; i<n; i++) {
L[i] = mx.walkleft(1, 0, n-1, h[i]+d);
mx.query(1, 0, n-1, i, h[i]);
}
mx = SegTree(n);
for (int i=n-1; i>=0; i--) {
R[i] = mx.walkright(1, 0, n-1, h[i]+d);
mx.query(1, 0, n-1, i, h[i]);
}
vector<int> towers;
for (int i=l; i <= r; i++) {
towers.push_back(i);
}
sort(towers.begin(), towers.end(), cmp);
SegTree st(n);
int cnt=0;
int m = towers.size();
for (int k=0; k<m; k++) {
int i = towers[k];
int i1 = st.rmq(1, 0, n-1, L[i], i);
int i2 = st.rmq(1, 0, n-1, i, R[i]);
if (i1 == i2 && i2 == 0) {
cnt++;
st.query(1, 0, n-1, i, 1);
}
}
return cnt;
}
