#include <bits/stdc++.h>
#include "towers.h"
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define sz(x) (signed)(x.size())
#define all(x) x.begin(),x.end()
#define unq(x) x.resize(unique(all(x))-x.begin())
#define For(i,l,r) for(int i=l;i<=r;i++)
#define ForD(i,r,l) for(int i=r;i>=l;i--)
#define endl '\n'
#define F "file"
#define fio freopen(F".inp","r",stdin);freopen(F".out","w",stdout);
using namespace std;
const int N=2e6+3;
int n,a[N],l1[N],r1[N],l2[N],r2[N],cnt=0;
int tin[N*3],tout[N*3],tdfs=0,par[20][N*3],chimto[N];
bool vs[N];
int ahihi[N];
pair<int,int> ln[N*3];
int sp[17][N];
bool b[N];
stack<int> sta;
set<pair<int,int>> st,st1;
map<pair<int,int>,int> mp;
vector<int> in[N],g[N*3];
pair<int,int> cucu[N*3];
vector<pair<int,int>> add;
void buildst() {
For(i,1,n) sp[0][i]=a[i];
For(j,1,16)
for(int i=1;i+(1<<j)-1<=n;i++) sp[j][i]=max(sp[j-1][i],sp[j-1][i+(1<<j-1)]);
}
void binbin() {
For(j,1,18)
For(i,1,cnt) par[j][i]=par[j-1][par[j-1][i]];
}
int binlift(int r,int u) {
int cur=u;
ForD(i,18,0) {
int x=par[i][cur];
if (ln[x].ss<=r) cur=x;
}
return cur;
}
int qr(int l,int r) {
int LG=__lg(r-l+1);
return max(sp[LG][l],sp[LG][r-(1<<LG)+1]);
}
struct PSeg {
int st[5*N],lf[5*N],rg[5*N],nd=0,cur=1,nn=0;
void init(int id,int l,int r) {
st[id]=0;
if (l==r) {
nd=max(nd,id);
return;
}
int mid=l+r>>1;
init(id*2,l,mid);
init(id*2+1,mid+1,r);
lf[id]=id*2,rg[id]=id*2+1;
}
int update(int id,int l,int r,int u,int x) {
if (l>u || r<u) return id;
if (l==r) {
st[++nd]=st[id]+x;
return nd;
}
int mid=l+r>>1;
int nw=++nd;
lf[nw]=lf[id],rg[nw]=rg[id];
if (u<=mid) lf[nw]=update(lf[id],l,mid,u,x);
else rg[nw]=update(rg[id],mid+1,r,u,x);
st[nw]=st[lf[nw]]+st[rg[nw]];
if (l==1 && r==nn) cur=nw;
return nw;
}
int query(int id,int l,int r,int u,int v) {
if (l>v || r<u) return 0;
if (l>=u && r<=v) return st[id];
int mid=l+r>>1;
return query(lf[id],l,mid,u,v)+query(rg[id],mid+1,r,u,v);
}
} tr,ed;
pair<int,int> addLine(int l,int r,int x,int idx) {
int hihi=ed.update(ed.cur,1,n,r,x);
int cur69=tr.update(tr.cur,1,cnt,tin[idx],x);
if (tout[idx]+1<=cnt) cur69=tr.update(tr.cur,1,cnt,tout[idx]+1,-x);
return {hihi,cur69};
}
int max_towers(int l,int r,int d) {
l++,r++;
pair<int,int> chim=cucu[(lower_bound(all(add),make_pair(d,(int)-2e9))-add.begin())];
int ans=ed.query(chim.ff,1,n,1,r);
if (l>1) {
ans-=ed.query(chim.ff,1,n,1,l-1);
int hihi=-1,haha=-1;
if (l1[l]!=-1) hihi=l2[l];
if (r1[l-1]!=n+1) haha=r2[l-1];
if (hihi==-1 || (haha!=-1 && ln[hihi].ss-ln[hihi].ff>ln[haha].ss-ln[haha].ff)) hihi=haha;
if (ln[hihi].second<=r) {
int xd=binlift(r,hihi);
ans-=tr.query(chim.ss,1,cnt,1,tin[hihi]);
if (par[0][xd]!=0) ans+=tr.query(chim.ss,1,cnt,1,tin[par[0][xd]]);
}
}
return r-l+1-ans;
}
void dfs(int u,int p=0) {
vs[u]=1;
tin[u]=++tdfs;
for(auto v: g[u])
if (!vs[v]) dfs(v,u);
tout[u]=tdfs;
}
void init(int N,vector<int> H) {
n=N;
For(i,0,n-1) a[i+1]=H[i];
fill(l1,l1+1+n,-1);
fill(r1,r1+1+n,n+1);
fill(ahihi,ahihi+1+n,-1);
ln[0]={-1e9,1e9};
ln[1]={1,n};
mp[{1,n}]=1;
cnt=1;
in[n].pb(1);
For(i,1,n) {
while (sz(sta) && a[sta.top()]>a[i]) {
r1[sta.top()]=i;
sta.pop();
}
sta.push(i);
}
while(sz(sta)) sta.pop();
ForD(i,n,1) {
while (sz(sta) && a[sta.top()]>a[i]) {
l1[sta.top()]=i;
sta.pop();
}
sta.push(i);
}
buildst();
For(i,1,n) {
if (l1[i]!=-1) {
if (!mp.count({l1[i],i})) {
ln[++cnt]={l1[i],i};
mp[{l1[i],i}]=cnt;
}
int idx=mp[{l1[i],i}];
l2[i]=idx;
in[i].pb(idx);
add.pb({qr(l1[i],i)-a[i],idx});
}
if (r1[i]!=n+1) {
if (!mp.count({i,r1[i]})) {
ln[++cnt]={i,r1[i]};
mp[{i,r1[i]}]=cnt;
}
int idx=mp[{i,r1[i]}];
r2[i]=idx;
in[r1[i]].pb(idx);
add.pb({qr(i,r1[i])-a[i],idx});
}
if (l1[i]!=-1 && r1[i]!=n+1) {
if (!mp.count({l1[i],r1[i]})) {
ln[++cnt]={l1[i],r1[i]};
mp[{l1[i],r1[i]}]=cnt;
}
int idx=mp[{l1[i],r1[i]}];
in[r1[i]].pb(idx);
add.pb({max(qr(l1[i],i)-a[i],qr(i,r1[i])-a[i]),-idx});
}
}
ForD(i,n,1) {
st1.clear();
for(auto x: in[i]) st1.insert({-ln[x].ff,x});
bool check=0;
for(auto x: in[i]) {
auto kk=st1.upper_bound({-ln[x].ff,1e9});
if (kk!=st1.end()) {
g[kk->ss].pb(x);
par[0][x]=kk->ss;
check=1;
} else {
auto kk1=st.lower_bound({-ln[x].ff,-1});
if (kk1!=st.end() && kk1->ss!=x) {
g[kk1->ss].pb(x);
par[0][x]=kk1->ss;
}
}
st.insert({-ln[x].ff,x});
}
for(auto x: in[i]) {
if (chimto[ln[x].ff]!=0) {
int idx=chimto[ln[x].ff];
st.erase(st.find({-ln[idx].ff,idx}));
}
chimto[ln[x].ff]=x;
st.insert({-ln[x].ff,x});
}
}
dfs(1,0);
binbin();
tr.nn=cnt,ed.nn=n;
tr.init(1,1,cnt);
ed.init(1,1,n);
cucu[0]={1,1};
sort(all(add));
For(i,1,sz(add)) {
int hihi=add[i-1].ss;
if (hihi>0) cucu[i]=addLine(ln[hihi].ff,ln[hihi].ss,1,hihi);
else cucu[i]=addLine(ln[-hihi].ff,ln[-hihi].ss,-1,-hihi);
}
}
