#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e5;
const int INF = 1e9+7;
int N, A[MAXN+10], B[MAXN+10], P[MAXN+10];
vector<int> comp;
struct SEG
{
int tree[MAXN*4+10];
void init(int node, int tl, int tr)
{
if(tl==tr)
{
tree[node]=A[tl];
return;
}
int mid=tl+tr>>1;
init(node*2, tl, mid);
init(node*2+1, mid+1, tr);
tree[node]=min(tree[node*2], tree[node*2+1]);
}
int query(int node, int tl, int tr, int l, int r)
{
if(r<tl || tr<l) return INF;
if(l<=tl && tr<=r) return tree[node];
int mid=tl+tr>>1;
return min(query(node*2, tl, mid, l, r), query(node*2+1, mid+1, tr, l, r));
}
}seg;
struct SEG2
{
int tree[MAXN*4+10];
void init(int node, int tl, int tr)
{
if(tl==tr)
{
tree[node]=P[tl];
return;
}
int mid=tl+tr>>1;
init(node*2, tl, mid);
init(node*2+1, mid+1, tr);
tree[node]=max(tree[node*2], tree[node*2+1]);
}
int query1(int node, int tl, int tr, int l, int r, int D)
{
if(r<tl || tr<l) return -1;
if(l<=tl && tr<=r && tree[node]<D) return -1;
if(tl==tr) return tl;
int mid=tl+tr>>1;
int ret=query1(node*2, tl, mid, l, r, D);
if(ret!=-1) return ret;
ret=query1(node*2+1, mid+1, tr, l, r, D);
return ret;
}
int query2(int node, int tl, int tr, int l, int r, int D)
{
if(r<tl || tr<l) return -1;
if(l<=tl && tr<=r && tree[node]<D) return -1;
if(tl==tr) return tl;
int mid=tl+tr>>1;
int ret=query2(node*2+1, mid+1, tr, l, r, D);
if(ret!=-1) return ret;
ret=query2(node*2, tl, mid, l, r, D);
return ret;
}
}seg2;
struct PST
{
struct Node
{
int val, lc, rc;
Node() : val(0), lc(-1), rc(-1) {}
};
vector<Node> NS;
int tree[MAXN+10];
int newNode()
{
NS.push_back(Node());
return NS.size()-1;
}
int makeTree(int tl, int tr)
{
int node=newNode();
if(tl==tr) return node;
int mid=tl+tr>>1;
NS[node].lc=makeTree(tl, mid);
NS[node].rc=makeTree(mid+1, tr);
return node;
}
int addTree(int node, int tl, int tr, int p)
{
if(p<tl || tr<p) return node;
int now=newNode();
if(tl==tr)
{
NS[now].val=NS[node].val+1;
return now;
}
int mid=tl+tr>>1;
NS[now].lc=addTree(NS[node].lc, tl, mid, p);
NS[now].rc=addTree(NS[node].rc, mid+1, tr, p);
NS[now].val=NS[NS[now].lc].val+NS[NS[now].rc].val;
return now;
}
int query(int node, int tl, int tr, int l, int r)
{
if(l<=tl && tr<=r) return NS[node].val;
if(r<tl || tr<l) return 0;
int mid=tl+tr>>1;
return query(NS[node].lc, tl, mid, l, r)+query(NS[node].rc, mid+1, tr, l, r);
}
}pst;
void init(int _N, vector<int> _H)
{
N=_N;
for(int i=1; i<=N; i++) A[i]=_H[i-1];
seg.init(1, 1, N);
vector<int> V;
V.push_back(1);
for(int i=2; i<=N; i++)
{
if(V.size()%2)
{
if(A[V.back()]<A[i]) V.push_back(i);
else V.back()=i;
}
else
{
if(A[V.back()]>A[i]) V.push_back(i);
else V.back()=i;
}
}
if(V.size()%2==0) V.pop_back();
set<int> S;
set<pii> S2;
for(int i=0; i<V.size(); i++)
{
S.insert(V[i]);
if(i%2==0) B[V[i]]=1;
else B[V[i]]=2;
}
for(int i=0; i+1<V.size(); i++) S2.insert({abs(A[V[i+1]]-A[V[i]]), V[i]});
while(!S2.empty())
{
auto [val, p] = *S2.begin(); S2.erase(S2.begin());
auto it=S.find(p);
int l=-1, r=-1;
if(it!=S.begin())
{
int t1=*prev(it), t2=*it;
S2.erase({abs(A[t1]-A[t2]), t1});
l=t1;
}
if(next(next(it))!=S.end())
{
int t1=*next(it), t2=*next(next(it));
S2.erase({abs(A[t1]-A[t2]), t1});
r=t2;
}
if(l!=-1 && r!=-1) S2.insert({abs(A[r]-A[l]), l});
P[*next(it)]=val; P[*it]=val;
S.erase(*next(it));
S.erase(it);
}
for(int i=1; i<=N; i++) comp.push_back(P[i]);
sort(comp.begin(), comp.end());
comp.erase(unique(comp.begin(), comp.end()), comp.end());
pst.tree[0]=pst.makeTree(1, comp.size());
for(int i=1; i<=N; i++)
{
pst.tree[i]=pst.addTree(pst.tree[i-1], 1, comp.size(), lower_bound(comp.begin(), comp.end(), P[i])-comp.begin()+1);
}
seg2.init(1, 1, N);
}
int max_towers(int L, int R, int D)
{
L++; R++;
int t=lower_bound(comp.begin(), comp.end(), D)-comp.begin()+1;
int ans=pst.query(pst.tree[R], 1, comp.size(), t, comp.size())-pst.query(pst.tree[L-1], 1, comp.size(), t, comp.size());
if(!ans) return 1;
int p=seg2.query1(1, 1, N, L, R, D), q=seg2.query2(1, 1, N, L, R, D);
if(B[p]==2)
{
if(seg.query(1, 1, N, L, p-1)<=A[p]-D) ans++;
else ans--;
}
if(B[q]==2)
{
if(seg.query(1, 1, N, q+1, R)<=A[q]-D) ans++;
else ans--;
}
return ans/2+1;
}
