#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
using pl = pair<ll, ll>;
using vl = vector<ll>;
#define F(i, l, r) for (ll i = ll(l); i < ll(r); ++i)
#define FD(i, l, r) for (ll i = ll(l); i > ll(r); --i)
#define A(a) (a).begin(), (a).end()
#define K first
#define V second
template<typename T> struct SparseTable {
int n,log2=0;
function<T(T, T)> merge;
T id ;
vector<vector<T>> a = {{}};
SparseTable(const vector<T>& v, function<T(T, T)> _merge, T _id): merge(_merge), id(_id) {
n = v.size();
while((1<<log2) <= n) {
++log2;
}
a.resize(log2);
a[0] = v;
for(int i=1,len=1;i<log2;++i,len*=2) {
a[i].resize(n + 1 - (1<<i));
for(size_t j=0;j<a[i].size();++j) {
a[i][j] = merge(a[i-1][j], a[i-1][j + len]);
}
}
}
SparseTable(){}
T query(int l, int r) { // [l,r)
if (r <= l) return id;
int len = __lg(r-l);
return merge(a[len][l], a[len][r- (1<<len)]);
}
};
SparseTable<ll> spmin;
const int MAXN = 100010, INF = 1000000010;
namespace seg {
struct node{
vector<pl> vec;
vector<int> mn, mx;
node(){};
node(int value, int pos){
vec.emplace_back(value, pos);
mn.push_back(pos);
mx.push_back(pos);
}
node(node& a, node& b){
vec.resize(a.vec.size() + b.vec.size());
mn.resize(vec.size());
mx.resize(vec.size());
merge(a.vec.begin(), a.vec.end(), b.vec.begin(), b.vec.end(), vec.begin());
int mi=MAXN, ma=-1;
FD(i, ll(vec.size())-1, -1) {
mi=min(mi, vec[i].V);
ma=max(ma, vec[i].V);
mn[i]=mi, mx[i]=ma;
}
}
};
node tr[2*MAXN];
pair<int, pl> query(int l, int r, int x){
int ret=0, mn=INF, mx=-1;
auto handle = [&](node& cur) {
auto itr = lower_bound(A(cur.vec), pair(x, -1));
int pos = (int)(itr - cur.vec.begin());
ret += (int)(cur.vec.end() - itr);
if(itr!=cur.vec.end()) mn=min(mn, cur.mn[pos]), mx=max(mx, cur.mx[pos]);
};
for(l+=MAXN, r+=MAXN; l<r; l>>=1, r>>=1){
if(l&1) handle(tr[l++]);
if(r&1) handle(tr[--r]);
}
return {ret, {mn, mx}};
}
void build(vl res) {
F(i, 0, res.size()) seg::tr[MAXN+i]=seg::node(res[i], i);
FD(i, MAXN-1, -1) tr[i]=node(tr[i<<1], tr[i<<1|1]);
}
}
int arr[MAXN];
void init(int n, vector<int> H) {
vl maxl(n), maxr(n);
copy(A(H), arr);
spmin = SparseTable<ll>(H, [](ll a, ll b) {
return min(a, b);
}, INF);
F(i, 0, n) {
int x;
for(x=i-1; x!=-1 && H[x]<H[i]; x=maxl[x]);
maxl[i]=x;
if (~x) assert(H[x] > H[i]);
}
FD(i, n-1, -1) {
int x;
for(x=i+1; x!=n && H[x]<H[i]; x=maxr[x]);
maxr[i]=x;
}
vl res(n);
F(i, 0, n) {
int l = maxl[i], r = maxr[i];
int a = H[i] - spmin.query(l+1, i);
int b = H[i] - spmin.query(i+1, r);
res[i] = min(a, b);
}
seg::build(res);
}
int max_towers(int L, int R, int D) {
pair<int, pl> ans = seg::query(L, R+1, D);
if(ans.K == 0) return 1;
int sa = (spmin.query(L, ans.V.K) > arr[ans.V.K] - D);
int sb = (spmin.query(ans.V.V+1, R+1) > arr[ans.V.V] - D);
return max(0, ans.K - sa - sb) + 1;
}
