#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, a[100100], b[100100], typ[100100];
vector<int> T;
struct Node{
int x, l, r;
Node(){}
Node(int _x, int _l, int _r): x(_x), l(_l), r(_r) {}
};
struct PST{
Node tree[4004000];
int root[100100], pt1, pt2, sz;
void init(int n){
sz = n;
tree[0] = Node(0, -1, -1);
root[0] = 0;
pt1 = 1, pt2 = 1;
}
void add(){
tree[pt1] = tree[root[pt2-1]];
root[pt2] = pt1;
++pt1, ++pt2;
}
int _new(int i){
if (i!=-1) tree[pt1++] = tree[i];
else tree[pt1++] = Node(0, -1, -1);
return pt1-1;
}
void build(int i, int l, int r, int a[]){
if (l==r) {tree[i].x = a[l]; return;}
int m = (l+r)>>1;
tree[i].l = _new(tree[i].l);
tree[i].r = _new(tree[i].r);
build(tree[i].l, l, m, a); build(tree[i].r, m+1, r, a);
tree[i].x = tree[tree[i].l].x + tree[tree[i].r].x;
}
void update(int i, int l, int r, int s, int x){
if (r<s || s<l) return;
if (l==r) {tree[i].x = x; return;}
int m = (l+r)>>1;
tree[i].l = _new(tree[i].l);
tree[i].r = _new(tree[i].r);
update(tree[i].l, l, m, s, x); update(tree[i].r, m+1, r, s, x);
tree[i].x = tree[tree[i].l].x + tree[tree[i].r].x;
}
int query(int i, int l, int r, int s, int e){
if (i==-1) return 0;
if (r<s || e<l) return 0;
if (s<=l && r<=e) return tree[i].x;
int m = (l+r)>>1;
return query(tree[i].l, l, m, s, e) + query(tree[i].r, m+1, r, s, e);
}
int left_bound(int i, int l, int r, int s, int e){
if (r<s || e<l) return -1;
if (tree[i].x==0) return -1;
if (l==r) return l;
int m = (l+r)>>1;
int tmp = left_bound(tree[i].l, l, m, s, e);
if (tmp!=-1) return tmp;
return left_bound(tree[i].r, m+1, r, s, e);
}
int right_bound(int i, int l, int r, int s, int e){
if (r<s || e<l) return -1;
if (tree[i].x==0) return -1;
if (l==r) return l;
int m = (l+r)>>1;
int tmp = right_bound(tree[i].r, m+1, r, s, e);
if (tmp!=-1) return tmp;
return right_bound(tree[i].l, l, m, s, e);
}
void update(int s, int x){
update(root[pt2-1], 1, sz, s, x);
}
int query(int t, int l, int r){
return query(root[t], 1, sz, l, r);
}
int left_bound(int t, int l, int r){
return left_bound(root[t], 1, sz, l, r);
}
int right_bound(int t, int l, int r){
return right_bound(root[t], 1, sz, l, r);
}
}tree1;
struct Seg{
int tree[200200], sz;
void init(int n){
sz = n;
for (int i=sz;i<sz*2;i++) tree[i] = a[i-sz];
for (int i=sz-1;i;i--) tree[i] = min(tree[i<<1], tree[i<<1|1]);
}
int query(int l, int r){
++r;
int ret = 1e9;
for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
if (l&1) ret = min(ret, tree[l++]);
if (r&1) ret = min(ret, tree[--r]);
}
return ret;
}
}tree2;
set<int> st;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
int myabs(int x){
if (x<0) return -x;
return x;
}
int getd(int x){
auto iter = st.find(x);
if (iter==st.end() || next(iter)==st.end()) return -1;
return myabs(a[*next(iter)] - a[*iter]);
}
void init(int N, std::vector<int> H) {
n = N;
for (int i=1;i<=n;i++) a[i] = H[i-1];
int tl = 1, tr = n;
for (;tl<n;tl++) if (a[tl] < a[tl+1]) break;
for (;tr>1;tr--) if (a[tr-1] > a[tr]) break;
assert(tl<=tr);
st.insert(tl);
st.insert(tr);
b[tl] = b[tr] = 1;
typ[tl] = typ[tr] = -1;
for (int i=tl+1;i<tr;i++){
if (a[i-1] < a[i] && a[i] > a[i+1]){
b[i] = 1, typ[i] = 1;
st.insert(i);
}
if (a[i-1] > a[i] && a[i] < a[i+1]){
b[i] = 1, typ[i] = -1;
st.insert(i);
}
}
for (auto iter=st.begin();next(iter)!=st.end();iter++) pq.emplace(myabs(a[*next(iter)] - a[*iter]), *iter);
tree1.init(n);
tree1.build(0, 1, n, b);
tree2.init(n+1);
T.push_back(0);
while(!pq.empty()){
auto [d, i] = pq.top(); pq.pop();
if (getd(i)!=d) continue;
auto iter = st.find(i);
T.push_back(d);
tree1.add();
tree1.update(i, 0);
tree1.update(*next(iter), 0);
iter = st.erase(iter, next(next(iter)));
//for (auto &x:st) printf(" %d", x);
//printf("\n");
if (iter==st.begin() || iter==st.end()) continue;
//printf(" add: %d %d -> %d\n", *prev(iter), *iter, getd(*prev(iter)));
--iter;
pq.emplace(myabs(a[*next(iter)] - a[*iter]), *iter);
}
/*for (int i=1;i<=n;i++) printf("%d ", b[i]);
printf("\n");
for (int i=1;i<=n;i++) printf("%d ", typ[i]);
printf("\n");
for (auto &x:T) printf("%d ", x);
printf("\n");*/
//printf("%d\n", tree1.tree[0].x);
}
int max_towers(int l, int r, int D) {
++l, ++r;
int t = lower_bound(T.begin(), T.end(), D) - T.begin() - 1;
int ans = tree1.query(t, l, r);
//printf("%d -> ", ans);
if (ans==0) return 1;
int L = tree1.left_bound(t, l, r), R = tree1.right_bound(t, l, r);
assert(L!=-1);
assert(R!=-1);
if (typ[L]==1){
int tmp = tree2.query(l, L-1);
if (a[L] - tmp >= D) ans++;
else ans--;
}
if (ans==0) return 1;
if (typ[R]==1){
int tmp = tree2.query(R+1, r);
if (a[R] - tmp >= D) ans++;
else ans--;
}
assert(ans%2==1);
return (ans+1)/2;
}
