#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
stack<int> s;
int h[maxn];
int t[4*maxn];
int x[maxn];
void build(int i,int l,int r)
{
if(l==r)
{
t[i]=h[l];
return;
}
int m=(l+r)/2;
build(i*2,l,m);
build(i*2+1,m+1,r);
t[i]=max(t[i*2],t[i*2+1]);
}
int query(int i,int l,int r,int ql,int qr)
{
if(ql>qr)return 0;
if(ql<=l&&r<=qr)return t[i];
int m=(l+r)/2;
return max(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;
void init(int N, std::vector<int> H)
{
n=N;
for(int i=0;i<n;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]=0;
else if(rt[i]==-1)x[i]=query(1,0,n-1,lf[i],i)-h[i];
else if(lf[i]==-1)x[i]=query(1,0,n-1,i,rt[i])-h[i];
else x[i]=min(query(1,0,n-1,lf[i],i),query(1,0,n-1,i,rt[i]))-h[i];
//cout<<i<<" "<<x[i]<<endl;
}
//cout<<endl;
sort(x,x+n);
}
int max_towers(int L, int R, int D)
{
int ans=n;
int l=0,r=n-1;
while(l<=r)
{
int m=(l+r)/2;
if(x[m]>=D)
{
ans=m;
r=m-1;
}
else l=m+1;
}
return n-ans+1;
}
/*
7 4
10 20 60 40 50 30 70
0 6 10
0 6 20
0 6 30
0 6 40
*/
