#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int root = 0;
int par[N];
int L[N], R[N], mn[N];
struct ST {
vector<pair<int,int>> t;
int n;
ST(){}
ST(vector<int>&h) {
n = h.size();
t.resize(2*n);
for(int i = 0;i<n;i++)t[i+n] = {h[i], i};
for(int i = n-1;i>0;i--)t[i] = max(t[2*i], t[2*i+1]);
}
int query(int l, int r) {
l+=n,r+=n+1;
pair<int,int> ans = {-1, -1};
for(;l<r;l>>=1,r>>=1) {
if(l&1)ans = max(ans, t[l++]);
if(r&1)ans = max(ans, t[--r]);
}
return ans.second;
}
};
struct ST2 {
vector<int> t;
int n;
ST2(){}
ST2(vector<int>&h) {
n = h.size();
t.resize(2*n);
for(int i = 0;i<n;i++)t[i+n] = h[i];
for(int i = n-1;i>0;i--)t[i] = min(t[2*i], t[2*i+1]);
}
int query(int l, int r) {
l+=n,r+=n+1;
int ans = 2e9;
for(;l<r;l>>=1,r>>=1) {
if(l&1)ans = min(ans, t[l++]);
if(r&1)ans = min(ans, t[--r]);
}
return ans;
}
};
struct ST3 {
vector<vector<int>> t;
int n;
ST3(){}
ST3(vector<vector<int>>&h) {
n = h.size();
t.resize(2*n);
for(int i = 0;i<n;i++){
t[i+n]=h[i];
sort(t[i+n].begin(), t[i+n].end());
}
for(int i = n-1;i>0;i--){
merge(t[2*i].begin(), t[2*i].end(), t[2*i+1].begin(), t[2*i+1].end(), back_inserter(t[i]));
}
}
int query(int l, int r, int key) {
l+=n,r+=n+1;
int ans=0;
for(;l<r;l>>=1,r>>=1) {
if(l&1) {
ans+=upper_bound(t[l].begin(), t[l].end(), key) - t[l].begin();
l++;
}
if(r&1) {
--r;
ans+=upper_bound(t[r].begin(), t[r].end(), key) - t[r].begin();
}
}
return ans;
}
};
vector<int> H;
ST st;
ST2 st2;
ST3 st3;
int pref[N+1];
int build(int l, int r) {
if(r < l)return -1;
int p = st.query(l, r);
L[p] = build(l, p-1);
R[p] = build(p+1, r);
mn[p] = H[p];
if(L[p]!=-1)mn[p] = min(mn[p], mn[L[p]]);
if(R[p]!=-1)mn[p] = min(mn[p], mn[R[p]]);
return p;
}
void init(int n, std::vector<int> h) {
st = ST(h);
st2 = ST2(h);
H = h;
root = build(0, n-1);
for(int i = 0;i<n;i++) {
bool check=1;
if(i and H[i-1] < H[i])check=false;
if(i+1 < n and H[i+1] < H[i])check=false;
if(i)pref[i] =pref[i-1];
pref[i]+=check;
}
}
int query(int v, int l, int r, int MX, int D) {
if(l > r)return 0;
if(v == -1)return 0;
if(v > r) {
return query(L[v], l, r, MX, D);
}
if(v < l)
return query(R[v], l, r, MX, D);
int ans = 0;
if(st2.query(l, r) <= MX)ans=1;
ans = max(ans, query(L[v], l, v-1, H[v]-D, D)+query(R[v], v+1, r, H[v]-D, D));
return ans;
}
int query2(int v, int l, int r) {
if(l > r)return 0;
if(v == -1)return 0;
if(v>r)return query2(L[v], l, r);
if(v<l)return query2(R[v], l, r);
int ans=0;
if(L[v] < l and (R[v] == -1 or R[v] > r))return 1;
ans+=query2(L[v], l, r);
ans+=query2(R[v], l, r);
return ans;
}
int max_towers(int l, int r, int D) {
if(D == 1) {
if(l == r)return 1;
if(l + 1 == r)return 1;
int ans = pref[r-1]-pref[l];
if(r and H[r-1] > H[r])ans++;
if(l+1<H.size() and H[l+1] > H[l])ans++;
return ans;
}
return query(root, l, r, 2e9, D);
}
