#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using ll = long long;
using vll = vector<ll>;
int N;
vi H;
vi LS, RS;
vll dist, dist2;
struct segtree
{
int l;
int r;
int mx = 0;
segtree* left = NULL;
segtree* right = NULL;
segtree()
{
;
}
segtree(int L, int R)
{
l = L;
r = R;
if(l == r)
mx = H[l];
else
{
int m = (l + r)/2;
left = new segtree(l, m);
right = new segtree(m+1, r);
mx = max(left->mx, right->mx);
}
}
int rangemax(int L, int R)
{
if(R < l || r < L)
return -1;
else if(L <= l && r <= R)
return mx;
else
return max(left->rangemax(L, R), right->rangemax(L, R));
}
};
void init(int N_, vi H_)
{
N = N_;
H = H_;
LS = RS = vi(N, -1);
vi st;
st.push_back(-1);
for(int i = 0; i < N; i++)
{
while(st.back() != -1 && H[i] < H[st.back()])
st.pop_back();
LS[i] = st.back();
st.push_back(i);
}
// cerr << "A\n";
segtree ST(0, N-1);
// cerr << "B\n";
st.clear();
st.push_back(N);
for(int i = N-1; i >= 0; i--)
{
while(st.back() != N && H[i] < H[st.back()])
st.pop_back();
RS[i] = st.back();
st.push_back(i);
}
// cerr << "C\n";
for(int i = 0; i < N; i++)
{
dist.push_back(0);
ll lval = 1'000'000'001LL;
if(LS[i] != -1)
lval = ST.rangemax(LS[i]+1, i-1) - H[i];
ll rval = 1'000'000'001LL;
if(RS[i] != N)
rval = ST.rangemax(i+1, RS[i]-1) - H[i];
dist[i] = min(lval, rval);
// cerr << i << " : " << LS[i] << ' ' << RS[i] << ' ' << lval << ' ' << rval << '\n';
}
dist2 = dist;
sort(dist2.begin(), dist2.end());
// cerr << "D\n";
}
int max_towers(int L, int R, int D)
{
// cerr << "enter\n";
int lo = 0, hi = N;
while(lo != hi)
{
int mid = (lo + hi)/2;
if(dist2[mid] < D)
lo = mid+1;
else
hi = mid;
}
// cerr << "exit\n";
return N - lo;
}
