#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rng(i,a,b) for(int i=int(a);i<=int(b);i++)
#define rep(i,b) rng(i,0,b-1)
#define gnr(i,b,a) for(int i=int(b);i>=int(a);i--)
#define per(i,b) gnr(i,b-1,0)
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;
using pii=pair<int,int>;
using vi=vc<int>;
using uint=unsigned;
using ull=unsigned ll;
using pil=pair<int,ll>;
using pli=pair<ll,int>;
using pll=pair<ll,ll>;
using t3=tuple<int,int,int>;
#define N_ 101000
#define SZ 131072
int chk, w[N_], n, INF = 1e9 + 123;
//vi V;
struct Tree{
pii IT[SZ+SZ];
void Put(int a, int b){
IT[a+SZ]={b,a};
a+=SZ;
while(a!=1){
a>>=1;
IT[a]=max(IT[a*2],IT[a*2+1]);
}
}
pii Get(int b, int e){
pii r={-INF,0};
b+=SZ,e+=SZ;
while(b<=e){
r=max({r,IT[b],IT[e]});
b=(b+1)>>1,e=(e-1)>>1;
}
return r;
}
}T1,T2,U1,U2;
pii Max(int b, int e){
return T1.Get(b,e);
}
pii Min(int b, int e){
auto z = T2.Get(b,e);
return {-z.fi, z.se};
}
struct Node{
pii Mn, Mx;
t3 ud, du;
}IT[SZ+SZ];
Node Merge (Node a, Node b){
Node r;
r.Mn = min(a.Mn,b.Mn);
r.Mx = max(a.Mx,b.Mx);
r.ud = max({a.ud, b.ud, {a.Mx.fi - b.Mn.fi, a.Mx.se, b.Mn.se} });
r.du = max({a.du, b.du, {b.Mx.fi - a.Mn.fi, a.Mn.se, b.Mx.se} });
return r;
}
void Put(int a){
Node t = {{w[a],a}, {w[a],a}, {0,a,a}, {0,a,a}};
a+=SZ;
IT[a] = t;
while(a!=1){
a>>=1;
IT[a] = Merge(IT[a*2],IT[a*2+1]);
}
}
Node GetRange(int b, int e){
b+=SZ,e+=SZ;
vi TL, TR;
while(b<=e){
if(b&1)TL.pb(b);
if(!(e&1))TR.pb(e);
b=(b+1)>>1,e=(e-1)>>1;
}
reverse(all(TR));
for(auto &t : TR)TL.pb(t);
Node res = IT[TL[0]];
rng(i,1,si(TL)-1){
res = Merge(res, IT[TL[i]]);
}
return res;
}
int U[N_];
int isUp[N_];
priority_queue<t3>PQ;
set<int>Set;
void SetPut(int x, int d){
auto it = Set.find(x);
auto it2 = it;
auto it3 = it;
it2--;
it3++;
if(*it2 == 0){
if(x>1){
if(isUp[x]){
auto [gg,u] = Min(1,x-1);
if(w[x] > w[u]){
PQ.push({w[x]-w[u], 0, u});
}
}
else{
auto [gg,u] = Max(1,x-1);
if(w[x] < w[u]){
PQ.push({w[u]-w[x], 0, u});
isUp[u] = 1;
}
}
}
}
else{
int b = (*it2) + 1, e = (*it)-1;
if(b<=e){
if(isUp[x]){
auto [p1,p2,p3,p4] = GetRange(b,e);
if(get<0>(p3)>0){
PQ.push(p3);
isUp[get<1>(p3)] = 1;
}
}
else{
auto [p1,p2,p3,p4] = GetRange(b,e);
if(get<0>(p4)>0){
PQ.push(p4);
isUp[get<2>(p4)] = 1;
}
}
}
}
if(*it3 == n+1){
if(x<n){
if(isUp[x]){
auto [gg,u] = Min(x+1,n);
if(w[x] > w[u]){
PQ.push({w[x]-w[u], 0, u});
}
}
else{
auto [gg,u] = Max(x+1,n);
if(w[x] < w[u]){
PQ.push({w[u]-w[x], 0, u});
isUp[u] = 1;
}
}
}
}
else{
int b = (*it) + 1, e = (*it3)-1;
if(b<=e){
if(!isUp[x]){
auto [p1,p2,p3,p4] = GetRange(b,e);
if(get<0>(p3)>0){
PQ.push(p3);
isUp[get<1>(p3)] = 1;
}
}
else{
auto [p1,p2,p3,p4] = GetRange(b,e);
if(get<0>(p4)>0){
PQ.push(p4);
isUp[get<2>(p4)] = 1;
}
}
}
}
}
int Root[N_];
struct PNode{
int l, r, s;
};
PNode PST[N_*30];
int cnt;
void Add(int nd, int p, int l, int r, int x){
PST[nd] = PST[p];
int m = (l+r)>>1;
PST[nd].s++;
if(l==r)return;
if(x<=m){
PST[nd].l = ++cnt;
Add(PST[nd].l, PST[p].l, l, m, x);
}
else{
PST[nd].r = ++cnt;
Add(PST[nd].r, PST[p].r, m+1, r, x);
}
}
int Sum(int nd, int b, int e, int s, int l){
if(s<=b&&e<=l)return PST[nd].s;
if(s>l)return 0;
int m = (b+e)>>1;
int rr = 0;
if(s<=m)rr += Sum(PST[nd].l, b, m, s, l);
if(l>m) rr += Sum(PST[nd].r, m+1, e, s, l);
return rr;
}
int Left(int nd, int b, int e, int s, int l){
if(!PST[nd].s)return -1;
if(b==e)return b;
int m = (b+e)>>1;
int rr = 0;
if(s<=m){
rr = Left(PST[nd].l, b, m, s, l);
if(rr!=-1)return rr;
}
return Left(PST[nd].r, m+1, e, s, l);
}
int Right(int nd, int b, int e, int s, int l){
if(!PST[nd].s)return -1;
if(b==e)return b;
int m = (b+e)>>1;
int rr = 0;
if(l>m){
rr = Right(PST[nd].r, m+1, e, s, l);
if(rr!=-1)return rr;
}
return Right(PST[nd].l, b, m, s, l);
}
vc<pii>V;
void init(int N, std::vector<int> H) {
n = N;
rng(i,1,N){
w[i] = H[i-1];
T1.Put(i,w[i]);
T2.Put(i,-w[i]);
}
rng(i,1,n){
Put(i);
}
auto [p1, p2, p3, p4] = GetRange(1,n);
Set.insert(0);
Set.insert(n+1);
{
if(get<0>(p3) < get<0>(p4)){
PQ.push(p4);
isUp[get<2>(p4)] = 1;
}
else{
PQ.push(p3);
isUp[get<1>(p3)] = 1;
}
}
while(!PQ.empty()){
auto [d,l,r] = PQ.top();
//printf("! %d %d %d\n",d,l,r);
PQ.pop();
if(l!=0){
Set.insert(l);
if(!U[l])U[l] = d;
}
Set.insert(r);
if(!U[r])U[r] = d;
if(l)SetPut(l,d);
SetPut(r,d);
}
rng(i,1,n){
V.pb({U[i],i});
U1.Put(i, U[i]);
}
sort(all(V));
per(i,n){
Root[i] = ++cnt;
Add(Root[i], Root[i+1], 1, n, V[i].se);
}
}
int max_towers(int L, int R, int D) {
L++,R++;
int pv = lower_bound(all(V), pii(D,-999)) - V.begin();
int c = Sum(Root[pv], 1, n, L, R);
if(!c)return 1;
int bb = Left(Root[pv], 1, n, L, R);
int ee = Right(Root[pv], 1, n, L, R);
if(isUp[bb]){
if(w[bb] - Min(L,bb-1).fi>= D) c++;
else c--;
}
if(isUp[ee]){
if(w[ee] - Min(ee+1,R).fi>= D) c++;
else c--;
}
return max(1,(c+1)/2);
}
