#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
int n,h[100001];
void init(int N, std::vector<int> H)
{
n=N;
for(int i=0;i<n;i++)
h[i]=H[i];
return;
}
int lf[100001];
int rt[100001];
vector<pair<int,int> > v;
int t[400001];
void upd(int i,int l,int r,int id,int vl)
{
if(l==r)
{
t[i]+=vl;
return;
}
int m=(l+r)/2;
if(id<=m)upd(i*2,l,m,id,vl);
else upd(i*2+1,m+1,r,id,vl);
t[i]=max(t[i*2],t[i*2+1]);
}
int query(int i,int l,int r)
{
if(l==r)return l;
int m=(l+r)/2;
if(t[i*2]!=0)return query(i*2,l,m);
else return query(i*2+1,m+1,r);
}
int max_towers(int L, int R, int D)
{
deque<int> a;
for(int i=0;i<n;i++)
{
while(a.size()&&h[a.back()]<h[i])a.pop_back();
a.push_back(i);
int id=-1;
int l=0,r=a.size()-1;
while(l<=r)
{
int m=(l+r)/2;
if(h[a[m]]>=h[i]+D)
{
id=a[m];
l=m+1;
}
else r=m-1;
}
lf[i]=id;
}
a.clear();
for(int i=n-1;i>=0;i--)
{
while(a.size()&&h[a.back()]<h[i])a.pop_back();
a.push_back(i);
int id=n;
int l=0,r=a.size()-1;
while(l<=r)
{
int m=(l+r)/2;
if(h[a[m]]>=h[i]+D)
{
id=a[m];
l=m+1;
}
else r=m-1;
}
rt[i]=id;
}
v.clear();
for(int i=L;i<=R;i++)
{
v.push_back({lf[i],rt[i]});
//cout<<i<<": "<<lf[i]<<" "<<rt[i]<<endl;
upd(1,0,n,rt[i],1);
}
sort(v.begin(),v.end());
int i=0,ans=0,last=-1;
while(1)
{
while(i<v.size()&&v[i].first<last)
{
//cout<<last<<" "<<v[i].first<<endl;
upd(1,0,n,v[i].second,-1);
i++;
}
//cout<<"! "<<i<<endl;
if(t[1]==0)break;
ans++;
last=query(1,0,n);
//cout<<v[i].first<<" "<<v[i].second<<" - "<<last<<endl;
}
return ans;
}
