#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
const int nx=1e5+5;
int n, vl[nx];
vector<int> h={0}, srt;
struct segtree
{
struct node
{
int mx, mn, difl, difr;
node(int mx=0, int mn=1e9, int difl=0, int difr=0): mx(mx), mn(mn), difl(difl), difr(difr){}
} d[4*nx];
node merge(node &l, node &r)
{
node res;
res.mx=max(l.mx, r.mx);
res.mn=min(l.mn, r.mn);
res.difl=max({l.difl, r.difl, r.mx-l.mn});
res.difr=max({l.difr, r.difr, l.mx-r.mn});
return res;
}
void build(int l, int r, int i)
{
if (l==r) return d[i]=node(h[l], h[l]), void();
int md=(l+r)/2;
build(l, md, 2*i);
build(md+1, r, 2*i+1);
d[i]=merge(d[2*i], d[2*i+1]);
}
int getmax(int l, int r, int i, int ql, int qr)
{
if (qr<l||r<ql) return 0;
if (ql<=l&&r<=qr) return d[i].mx;
int md=(l+r)/2;
return max(getmax(l, md, 2*i, ql, qr), getmax(md+1, r, 2*i+1, ql, qr));
}
int getlessleft(int l, int r, int i, int idx, int vl)
{
if (idx<l||d[i].mn>=vl) return 0;
if (l==r) return d[i].mn<vl?l:0;
int md=(l+r)/2;
int lvl=getlessleft(md+1, r, 2*i+1, idx, vl);
return lvl?lvl:getlessleft(l, md, 2*i, idx, vl);
}
int getlessright(int l, int r, int i, int idx, int vl)
{
if (r<idx||d[i].mn>=vl) return 0;
if (l==r) return d[i].mn<vl?l:0;
int md=(l+r)/2;
int rvl=getlessright(l, md, 2*i, idx, vl);
return rvl?rvl:getlessright(md+1, r, 2*i+1, idx, vl);
}
} s;
void init(int N, std::vector<int> H) {
n=N;
for (int i=0; i<n;i ++) h.push_back(H[i]);
s.build(1, n, 1);
for (int i=1; i<=n; i++)
{
int cl=s.getlessleft(1, n, 1, i, h[i]), cr=s.getlessright(1, n, 1, i, h[i]), f=0;
if (cl&&cl+1==i) f=1;
if (cr&&cr-1==i) f=1;
if (!f)
{
if (cl&&cr) vl[i]=min(s.getmax(1, n, 1, cl+1, i-1), s.getmax(1, n, 1, i+1, cr-1));
else if (cr) vl[i]=s.getmax(1, n, 1, i+1, cr-1)-h[i];
else if (cl) vl[i]=s.getmax(1, n, 1, cl+1, i-1)-h[i];
else vl[i]=2e9;
}
//cout<<"debug "<<i<<' '<<h[i]<<' '<<cl<<' '<<cr<<' '<<vl[i]<<'\n';
if (vl[i]) srt.push_back(vl[i]);
}
sort(srt.begin(), srt.end());
}
int max_towers(int L, int R, int D) {
return srt.end()-lower_bound(srt.begin(), srt.end(), D);
}
