#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 {
pl merge(pl a, pl b) {
return pair(min(a.K, b.K), max(a.V, b.V));
}
struct node{
vector<pl> vec;
vector<pl> indices; // {mn, mx}
node(){};
node(int value, int pos){
vec.emplace_back(value, pos);
indices.emplace_back(pos, pos);
}
node(node& a, node& b){
vec.resize(a.vec.size() + b.vec.size());
indices.resize(vec.size());
merge(a.vec.begin(), a.vec.end(), b.vec.begin(), b.vec.end(), vec.begin());
pl cur(MAXN, -1);
// All items are now in sorted order, relative to first key.
// mn and max represent the range of indices
FD(i, ll(vec.size())-1, -1) indices[i] = cur = merge(pair(vec[i].V, vec[i].V), cur);
}
};
node tr[2*MAXN];
pair<int, pl> query(int l, int r, int x){
int cnt=0;
pl res(MAXN, -1);
auto handle = [&](node& cur) {
auto &[vec, indices] = cur;
auto itr = lower_bound(A(vec), pair(x, -1));
int pos = (int)(itr - vec.begin());
cnt += (int)(vec.end() - itr);
if(itr!=vec.end()) res = merge(res, indices[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 {cnt, res};
}
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;
}
FD(i, n-1, -1) {
int x;
for(x=i+1; x!=n && H[x]<H[i]; x=maxr[x]);
maxr[i]=x;
}
// maxl and maxr finds closest node greater than it to left and right ? not sure
vl res(n);
F(i, 0, n) {
int l = maxl[i], r = maxr[i];
// H[i] is trying to glue the left and right, so it must take the max of
// the two valleys to either side.
res[i] = H[i] - max(spmin.query(l+1, i), spmin.query(i+1, r));
}
seg::build(res);
}
int max_towers(int L, int R, int D) {
// Queries in the range [l, r] for all res values (peaks with glue value) >= D, and then returns
// how many items were in the range, the minimum indexed peak, and maximum indexed peak of said range.
auto [cnt, indices] = seg::query(L, R+1, D);
if(!cnt) return 1;
auto [mn, mx] = indices;
// we want to find something to lease to the left and right
// since we're only counting peaks (we actually lease valleys)
// we would like to lease (cnt+1) things since (cnt+1) gaps,
// but need to make sure endpoints are legit
bool sa = (D > arr[mn] - spmin.query(L, mn));
bool sb = (D > arr[mx] - spmin.query(mx+1, R+1));
return max(1, (cnt + 1) - sa - sb);
}
