#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
using pl = pair<ll, ll>;
#define F(i, l, r) for (ll i = (l); i < (r); ++i)
#define FD(i, l, r) for (ll i = (l); i > (r); --i)
#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;
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;
}
}
};
int n, arr[MAXN], ml[MAXN], mr[MAXN], res[MAXN];
node tr[2*MAXN];
pair<int, pl> query(int l, int r, int x){
int ret=0, mn=INF, mx=-1;
for(l+=n, r+=n; l<r; l>>=1, r>>=1){
if(l&1){
auto itr = lower_bound(tr[l].vec.begin(), tr[l].vec.end(), pair(x, -1));
int pos = (int)(itr - tr[l].vec.begin());
ret += (int)(tr[l].vec.end() - itr);
if(itr!=tr[l].vec.end()) mn=min(mn, tr[l].mn[pos]), mx=max(mx, tr[l].mx[pos]);
++l;
}
if(r&1){
--r;
auto itr = lower_bound(tr[r].vec.begin(), tr[r].vec.end(), pair(x, -1));
int pos = (int)(itr - tr[r].vec.begin());
ret += (int)(tr[r].vec.end() - itr);
if(itr!=tr[r].vec.end()) mn=min(mn, tr[r].mn[pos]), mx=max(mx, tr[r].mx[pos]);
}
}
return {ret, {mn, mx}};
}
void init(int N, vector<int> H) {
n=N;
F(i, 0, n) arr[i] = H[i];
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=ml[x]);
ml[i]=x;
}
FD(i, n-1, -1) {
int x;
for(x=i+1; x!=n && H[x]<H[i]; x=mr[x]);
mr[i]=x;
}
F(i, 0, n) {
int l = ml[i], r = mr[i];
int a = H[i] - spmin.query(l+1, i);
int b = H[i] - spmin.query(i+1, r);
res[i] = min(a, b);
}
F(i, 0, n) tr[n+i]=node(res[i], i);
FD(i, n-1, -1) tr[i]=node(tr[i<<1], tr[i<<1|1]);
}
int max_towers(int L, int R, int D) {
pair<int, pl> ans = 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;
}
