#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
stack<int> s;
struct node
{
int minn,maxx,diff,diff2;
node(){}
node(int mn,int mx,int df,int df2)
{
minn=mn;
maxx=mx;
diff=df;
diff2=df2;
}
};
int h[maxn];
node t[4*maxn];
int x[maxn];
node pull(node n1,node n2)
{
node r={min(n1.minn,n2.minn),max(n1.maxx,n2.maxx),max(n1.diff,n2.diff),max(n1.diff2,n2.diff2)};
r.diff=max(r.diff,n2.maxx-n1.minn);
r.diff2=max(r.diff2,n1.maxx-n2.minn);
return r;
}
void build(int i,int l,int r)
{
if(l==r)
{
t[i]={h[l],h[l],0,0};
return;
}
int m=(l+r)/2;
build(i*2,l,m);
build(i*2+1,m+1,r);
t[i]=pull(t[i*2],t[i*2+1]);
}
node query(int i,int l,int r,int ql,int qr)
{
if(ql>qr)return {(int)1e9,0,0,0};
if(ql<=l&&r<=qr)return t[i];
int m=(l+r)/2;
return pull(query(i*2,l,m,ql,min(qr,m)),query(i*2+1,m+1,r,max(ql,m+1),qr));
}
int lf[maxn];
int rt[maxn];
int n;
vector<int> c[4*maxn],minn[4*maxn],maxx[4*maxn];
bool cmp(int i,int j)
{
return x[i]>x[j];
}
void build2(int i,int l,int r)
{
if(l==r)
{
c[i].push_back(l);
minn[i].push_back(l);
maxx[i].push_back(l);
return;
}
int m=(l+r)/2;
build2(i*2,l,m);
build2(i*2+1,m+1,r);
//cout<<i<<" "<<l<<" "<<r<<endl;
c[i]=c[i*2+1];
for(int j=0;j<c[i*2].size();j++)
c[i].push_back(c[i*2][j]);
sort(c[i].begin(),c[i].end(),cmp);
minn[i]=maxx[i]=c[i];
minn[i][0]=maxx[i][0]=c[i][0];
for(int j=1;j<c[i].size();j++)
minn[i][j]=min(c[i][j],minn[i][j-1]),
maxx[i][j]=max(c[i][j],maxx[i][j-1]);
}
node qq[4*maxn];
int ll,rr,md,id;
node query2(int i,int l,int r,int ql,int qr,int vl)
{
if(ql>qr)return {(int)1e9,0,0,0};
if(ql<=l&&r<=qr)
{
id=-1;
ll=0,rr=c[i].size()-1;
while(ll<=rr)
{
int md=(ll+rr)/2;
if(x[c[i][md]]>=vl)
{
id=md;
ll=md+1;
}
else rr=md-1;
}
if(id==-1)return {(int)1e9,0,0,0};
else return {minn[i][id],maxx[i][id],id+1,0};
}
int m=(l+r)/2;
qq[i*2]=query2(i*2,l,m,ql,min(qr,m),vl);
qq[i*2+1]=query2(i*2+1,m+1,r,max(m+1,ql),qr,vl);
return {min(qq[i*2].minn,qq[i*2+1].minn),max(qq[i*2].maxx,qq[i*2+1].maxx),qq[i*2].diff+qq[i*2+1].diff,0};
}
int one;
void init(int N, std::vector<int> H)
{
n=N;
for(int i=0;i<n;i++)
{
if(i==0||H[i]>H[i-1])one=i;
h[i]=H[i];
while(s.size()&&h[s.top()]>h[i])s.pop();
if(s.size())lf[i]=s.top();
else lf[i]=-1;
s.push(i);
}
while(s.size())s.pop();
build(1,0,n-1);
for(int i=n-1;i>=0;i--)
{
while(s.size()&&h[s.top()]>h[i])s.pop();
if(s.size())rt[i]=s.top();
else rt[i]=-1;
s.push(i);
if(lf[i]==-1&&rt[i]==-1)x[i]=1e9;
else if(rt[i]==-1)x[i]=query(1,0,n-1,lf[i],i).maxx-h[i];
else if(lf[i]==-1)x[i]=query(1,0,n-1,i,rt[i]).maxx-h[i];
else x[i]=min(query(1,0,n-1,lf[i],i).maxx,query(1,0,n-1,i,rt[i]).maxx)-h[i];
//cout<<i<<" "<<x[i]<<endl;
}
build2(1,0,n-1);
//cout<<endl;
}
node q;
int l,r,m,id1,id2;
int max_towers(int L, int R, int D)
{
q=query2(1,0,n-1,L,R,D);
if(q.minn==1e9)return 1;
//cout<<q.minn<<" "<<q.maxx<<endl;
l=L,r=q.minn;
id1=-1;
while(l<=r)
{
m=(l+r)/2;
if(query(1,0,n-1,m,q.minn).maxx>=h[q.minn]+D)
{
id1=m;
l=m+1;
}
else r=m-1;
}
l=q.maxx,r=R;
id2=-1;
while(l<=r)
{
m=(l+r)/2;
//cout<<m<<" "<<R<<" - "<<query(1,0,n-1,m,R).maxx<<endl;
if(query(1,0,n-1,q.maxx,m).maxx>=h[q.maxx]+D)
{
id2=m;
r=m-1;
}
else l=m+1;
}
//cout<<id1<<" "<<id2<<endl;
if(id1!=-1&&query(1,0,n-1,L,id1).diff>=D)q.diff++;
if(id2!=-1&&query(1,0,n-1,id2,R).diff2>=D)q.diff++;
return q.diff;
}
/*
7 4
10 20 60 40 50 30 70
1 2 10
1 6 20
3 6 30
2 4 40
*/
