#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
int n,pos;
vector<int> h;
const int N = 2e5 + 12,B = 20;
int sp[20][N],p[20][N],lg[N],sp1[20][N],p1[20][N];
bool sub = false;
void build() {
for(int i = 0;i < n;i++){
sp1[0][i] = sp[0][i] = h[i];
p1[0][i] = p[0][i] = i;
}
for(int i = 1;i < B;i++) {
for(int j = 0;j + (1 << i) - 1 < n;j++) {
int X = sp[i - 1][j],Y = sp[i - 1][j + (1 << (i - 1))];
sp[i][j] = min(X,Y);
if(sp[i][j] == X) {
p[i][j] = p[i - 1][j];
}else {
p[i][j] = p[i - 1][j + (1 << (i - 1))];
}
X = sp1[i - 1][j],Y = sp1[i - 1][j + (1 << (i - 1))];
sp1[i][j] = max(X,Y);
if(sp1[i][j] == X) {
p1[i][j] = p1[i - 1][j];
}else {
p1[i][j] = p1[i - 1][j + (1 << (i - 1))];
}
}
}
}
pair<int,int> get(int L,int R) {
int i = lg[R - L + 1];
pair<int,int> x = make_pair(sp[i][L],p[i][L]);
pair<int,int> y = make_pair(sp[i][R - (1 << i) + 1],p[i][R - (1 << i) + 1]);
return min(x,y);
}
pair<int,int> get1(int L,int R) {
int i = lg[R - L + 1];
pair<int,int> x = make_pair(sp1[i][L],p1[i][L]);
pair<int,int> y = make_pair(sp1[i][R - (1 << i) + 1],p1[i][R - (1 << i) + 1]);
return max(x,y);
}
int _l[N],_r[N],val[N],_mx[N],_mn[N];
vector<int> b,t;
struct node {
bool e = true;
int mx = 0,mn = 1e9,ans = 0,ans1 = 0;
}T[N * 4];
node merge(node l,node r) {
if(l.e) return r;
if(r.e) return l;
node ret;
ret.e = false;
ret.mx = max(l.mx,r.mx);
ret.mn = min(l.mn,r.mn);
ret.ans = max({l.ans,r.ans,l.mx - r.mn});
ret.ans1 = max({l.ans1,r.ans1,r.mx - l.mn});
return ret;
}
void build_(int v = 1,int tl = 0,int tr = n - 1) {
if(tl == tr) {
T[v].mx = T[v].mn = h[tl];
T[v].e = false;
}else {
int tm = (tl + tr) >> 1;
build_(v + v,tl,tm);
build_(v + v + 1,tm + 1,tr);
T[v] = merge(T[v + v],T[v + v + 1]);
}
}
node Get(int l,int r,int v = 1,int tl = 0,int tr = n - 1) {
if(l > r || tl > r || l > tr) {
node f;return f;
}
if(tl >= l && tr <= r) return T[v];
int tm = (tl + tr) >> 1;
return merge(Get(l,r,v+v,tl,tm),Get(l,r,v+v+1,tm+1,tr));
}
struct Node{
Node *l = 0,*r = 0;
int mx = 0,mn = (int)1e9,s = 0;
Node (){}
Node (int val) {
mx= mn = val;
s = 1;
}
Node (Node *l_,Node *r_) {
l = l_;
r = r_;
mx = max(l->mx,r->mx);
mn = min(l->mn,r->mn);
s = l->s + r->s;
}
};
using pnode = Node *;
pnode t_[N];
pnode build1(int tl = 0,int tr = n - 1) {
if(tl == tr) return new Node();
int tm = (tl + tr) >> 1;
return new Node(build1(tl,tm),build1(tm + 1,tr));
}
pnode upd(pnode v,int pos,int tl = 0,int tr = n - 1) {
if(tl == tr) {
return new Node(tl);
} else {
int tm = (tl + tr) >> 1;
if(pos <= tm) {
return new Node(upd(v->l,pos,tl,tm),v->r);
}
return new Node(v->l,upd(v->r,pos,tm+1,tr));
}
}
int get_sum(int l,int r,pnode v,int tl = 0,int tr = n - 1) {
if(l > r || tl > r || l > tr) return 0;
if(tl >= l && tr <= r) {
return v->s;
}else {
int tm = (tl + tr) >> 1;
return get_sum(l,r,v->l,tl,tm) + get_sum(l,r,v->r,tm+1,tr);
}
}
int get_mx(int l,int r,pnode v,int tl = 0,int tr = n - 1) {
if(l > r || tl > r || l > tr) return 0;
if(tl >= l && tr <= r) {
return v->mx;
}else {
int tm = (tl + tr) >> 1;
return max(get_mx(l,r,v->l,tl,tm),get_mx(l,r,v->r,tm+1,tr));
}
}
int get_mn(int l,int r,pnode v,int tl = 0,int tr = n - 1) {
if(l > r || tl > r || l > tr) return (int)1e9;
if(tl >= l && tr <= r) {
return v->mn;
}else {
int tm = (tl + tr) >> 1;
return min(get_mn(l,r,v->l,tl,tm),get_mn(l,r,v->r,tm+1,tr));
}
}
void init(int nn, vector<int> H) {
n = nn;
h = H;
build();
build_();
for(int i = 2;i <= n;i++) {
lg[i] = lg[i / 2] + 1;
}
vector<int> st;
for(int i = 0;i < n;i++) {
while((int)st.size() && h[st.back()] > h[i]) {
st.pop_back();
}
_l[i] = (st.empty() ? -1 : st.back());
st.push_back(i);
}
st.clear();
for(int i = n - 1;i >= 0;i--) {
while(!st.empty() && h[st.back()] > h[i]) {
st.pop_back();
}
_r[i] = (st.empty() ? n : st.back());
st.push_back(i);
}
for(int i = 0;i < n;i++) {
val[i] = min(get1(_l[i] + 1,i).first,get1(i,_r[i]-1).first) - h[i];
t.push_back(i);
}
sort(t.begin(),t.end(),[&](int x,int y){
return val[x] < val[y];
});
for(int i:t) {
b.push_back(val[i]);
}
_mx[n - 1] = _mn[n - 1] = t.back();
for(int i = n - 2;i >= 0;i--) {
_mx[i] = max(t[i],_mx[i + 1]);
_mn[i] = min(t[i],_mn[i + 1]);
}
t_[n] = build1();
for(int i = n - 1;i >= 0;i--) {
// cout << i << ' ' << t[i] << ' ' << val[t[i]] << '\n';
t_[i] = upd(t_[i + 1],t[i]);
}
}
bool fq = true;
int up[N * 2][20],up1[N * 2][20];
int F(int x) {
if(x < n) return x;
return x - n;
}
bool solver(int x,int y,int d) {
int l = x,r = y + 1;
while(r - l > 1) {
int mid = (l + r) >> 1;
if(get1(x,mid).first >= h[x] + d) {
r = mid;
} else {
l = mid;
}
}
if(r == y + 1) {
return false;
}
x = r;
node _ = Get(x,y);
return (_.ans >= d);
}
bool solvel(int x,int y,int d) {
int l = x - 1,r = y;
while(r - l > 1) {
int mid = (l + r) >> 1;
if(get1(mid,y).first >= h[y] + d) {
l = mid;
}else {
r = mid;
}
}
// cout << x << ' ' << y << ' ' << l << '\n';
if(l == x - 1) return false;
y = l;
node _ = Get(x,y);
return (_.ans1 >= d);
}
int max_towers(int l_, int r_, int d) {
int it = lower_bound(b.begin(),b.end(),d) - b.begin();
int ret = 0;
int l,r;
if(it == (int)b.size()) {
l = r = get(l_,r_).second;
ret++;
} else {
l = get_mn(l_,r_,t_[it]);
r = get_mx(l_,r_,t_[it]);
ret = get_sum(l_,r_,t_[it]);
}
return ret + solvel(l_,l,d) + solver(r,r_,d);
}
