#include "towers.h"
#include <iostream>
#include <vector>
#include <array>
#include <map>
#define ll long long
using namespace std;
array<ll, 2> R[100000];
ll X[400000];
struct SegTree{
vector <ll> A;
ll mn[400000], mx[400000];
void build(ll id, ll l, ll r) {
if (l == r) {
mn[id] = mx[id] = A[l];
return;
}
ll mid = (l+r)/2;
build(id*2, l, mid);
build(id*2+1, mid+1, r);
mn[id] = min(mn[id*2], mn[id*2+1]);
mx[id] = max(mx[id*2], mx[id*2+1]);
}
ll rhsmaxid(ll id, ll l, ll r, ll ql, ll qr, ll w) {
if (qr < l || r < ql || mx[id] < w || ql > qr) return 1e18;
else if (ql <= l && r <= qr) {
if (l == r) return l;
ll mid = (l+r)/2;
if (mx[id*2] >= w) return rhsmaxid(id*2, l, mid, ql, qr, w);
else return rhsmaxid(id*2+1, mid+1, r, ql, qr, w);
}
ll mid = (l+r)/2;
ll res = rhsmaxid(id*2, l, mid, ql, qr, w);
if (res != 1e18) return res;
else return rhsmaxid(id*2+1, mid+1, r, ql, qr, w);
}
ll lhsmaxid(ll id, ll l, ll r, ll ql, ll qr, ll w) {
if (qr < l || r < ql || mx[id] < w || ql > qr) return -1e18;
else if (ql <= l && r <= qr) {
if (l == r) return l;
ll mid = (l+r)/2;
if (mx[id*2+1] >= w) return lhsmaxid(id*2+1, mid+1, r, ql, qr, w);
else return lhsmaxid(id*2, l, mid, ql, qr, w);
}
ll mid = (l+r)/2;
ll res = lhsmaxid(id*2+1, mid+1, r, ql, qr, w);
if (res != -1e18) return res;
else return lhsmaxid(id*2, l, mid, ql, qr, w);
}
ll querymin(ll id, ll l, ll r, ll ql, ll qr) {
if (qr < l || r < ql || ql > qr) return 1e18;
else if (ql <= l && r <= qr) return mn[id];
ll mid = (l+r)/2;
return min(querymin(id*2, l, mid, ql, qr), querymin(id*2+1, mid+1, r, ql, qr));
}
}ST, ST2;
struct PersistentSegTree{
struct Node{
ll val = 0;
ll chl = -1;
ll chr = -1;
};
vector <Node> st;
ll getNew() {
st.push_back({0, -1, -1});
return (ll)st.size()-1;
}
void update(ll id, ll nid, ll l, ll r, ll q) {
if (l == r) {
st[nid].val = (id == -1 ? 0 : st[id].val) + 1;
return;
}
ll mid = (l+r)/2;
if (q <= mid) {
st[nid].chl = getNew(), st[nid].chr = (id == -1 ? -1 : st[id].chr);
update((id == -1 ? -1 : st[id].chl), st[nid].chl, l, mid, q);
}
else {
st[nid].chl = (id == -1 ? -1 : st[id].chl), st[nid].chr = getNew();
update((id == -1 ? -1 : st[id].chr), st[nid].chr, mid+1, r, q);
}
st[nid].val = st[st[nid].chl].val + st[st[nid].chr].val;
}
ll query(ll id, ll l, ll r, ll ql, ll qr) {
if (qr < l || r < ql || id == -1) return 0;
else if (ql <= l && r <= qr) return st[id].val;
ll mid = (l+r)/2;
return query(st[id].chl, l, mid, ql, qr) + query(st[id].chr, mid+1, r, ql, qr);
}
}PST;
vector <ll> rt;
map <ll, ll> mp;
vector <ll> H, Z;
ll n;
void init(int N, std::vector<int> height) {
n = N;
for (auto u : height) {
H.push_back(u);
ST.A.push_back(u);
}
ST.build(1, 0, N-1);
for (int i=0; i<N; ++i) {
R[i] = {ST.lhsmaxid(1, 0, N-1, 0, i-1, H[i]), ST.rhsmaxid(1, 0, N-1, i+1, N-1, H[i])};
X[i] = max(0LL, H[i] - max(ST.querymin(1, 0, N-1, max(0LL, R[i][0]+1), i), (ST.querymin(1, 0, N-1, i, min((ll)N-1, R[i][1]-1)))));
++mp[X[i]];
ST2.A.push_back(X[i]);
}
ll k = 0;
for (auto [x, y] : mp) {
mp[x] = k++;
}
ST2.build(1, 0, N-1);
rt.push_back(PST.getNew());
for (int i=0; i<N; ++i) {
auto nrt = PST.getNew();
PST.update(rt.back(), nrt, 0, mp.size()-1, mp[X[i]]);
rt.push_back(nrt);
}
return;
}
bool check(ll u, ll l, ll r, ll d) {
if (u == 1e18) return 0;
auto res = max(ST.querymin(1, 0, n-1, max(l, R[u][0]+1), u), (ST.querymin(1, 0, n-1, u, min(r, R[u][1]-1))));
if (H[u] >= res+d) return 1;
else return 0;
}
int max_towers(int L, int R, int D) {
ll ql = ST2.rhsmaxid(1, 0, n-1, L, R, D);
if (!check(ql, L, R, D)) {
ql = ST2.rhsmaxid(1, 0, n-1, ql+1, R, D);
if (!check(ql, L, R, D)) return 1;
}
ll qr = ST2.lhsmaxid(1, 0, n-1, L, R, D);
if (!check(qr, L, R, D)) {
qr = ST2.lhsmaxid(1, 0, n-1, L, qr-1, D);
if (!check(qr, L, R, D)) return 1;
}
if (ql == qr) return 2;
auto it = mp.lower_bound(D);
ll f = 3 + PST.query(rt[qr], 0, mp.size()-1, it->second, mp.size()-1) - PST.query(rt[ql+1], 0, mp.size()-1, it->second, mp.size()-1);
return f;
}
