#include "towers.h"
#include <vector>
#include <bits/stdc++.h>
#define pii pair<int,int>
#define fs first
#define sc second
using namespace std;
const int B = 20;
const int mxn = 1e5+10;
const int inf = 1e9;
int N;
vector<int> H;
int par[mxn][B];
pii tree[mxn];
int arr[mxn];
int rt;
int dep[mxn];
pii big[mxn];
pii eul[mxn];
int dp[mxn];
multiset<int> st[mxn];
void dfs(int now){
for(int i = 1;i<B;i++)par[now][i] = par[par[now][i-1]][i-1];
eul[now] = pii(now,now);
if(tree[now].fs){
int nxt = tree[now].fs;
assert(arr[now]>arr[nxt]);
dep[nxt] = dep[now]+1;
par[nxt][0] = now;
dfs(nxt);
eul[now].fs = eul[nxt].fs;
}
if(tree[now].sc){
int nxt = tree[now].sc;
assert(arr[now]>arr[nxt]);
dep[nxt] = dep[now]+1;
par[nxt][0] = now;
dfs(nxt);
eul[now].sc = eul[nxt].sc;
}
return;
}
void add(int now,int tar,int val,int D){
int pos = now;
for(int i = B-1;i>=0;i--){
int p = par[now][i];
if(arr[p]<tar)now = p;
}
if(arr[now]<tar)now = par[now][0];
if(arr[now]<tar)return;
int side = 0;
int rs = tree[now].sc;
if(rs&&eul[rs].fs<=pos&&eul[rs].sc>=pos)side = 1;
if(!side)big[now].fs = max(big[now].fs,val);
else big[now].sc = max(big[now].sc,val);
return;
}
int dfs1(int now,int D){
st[now].clear();
big[now].fs = big[now].sc = 0;
dp[now] = 1;
if(!tree[now].fs&&!tree[now].sc)st[now].insert(arr[now]);
if(tree[now].fs){
int nxt = tree[now].fs;
dfs1(nxt,D);
dp[now] = max({dp[now],(int)st[nxt].size(),dp[nxt]});
while(!st[nxt].empty()&&*st[nxt].rbegin()+D)st[nxt].erase(st[nxt].find(*st[nxt].rbegin()));
if(st[now].size()<st[nxt].size())st[now].swap(st[nxt]);
for(auto &i:st[nxt])st[now].insert(i);
}
if(tree[now].sc){
int nxt = tree[now].fs;
dfs1(nxt,D);
dp[now] = max({dp[now],(int)st[nxt].size(),dp[nxt]});
while(!st[nxt].empty()&&*st[nxt].rbegin()+D<arr[now])st[nxt].erase(st[nxt].find(*st[nxt].rbegin()));
if(st[now].size()<st[nxt].size())st[now].swap(st[nxt]);
for(auto &i:st[nxt])st[now].insert(i);
}
cerr<<now<<":";for(auto &j:st[now])cerr<<j<<',';cerr<<endl;
dp[now] = max(dp[now],(int)st[now].size());
return dp[now];
}
void build(int s,int e){
for(auto &i:tree)i = pii(0,0);
vector<int> st;
for(int i = s;i<=e;i++){
while(!st.empty()&&arr[st.back()]<arr[i]){
tree[i].fs = st.back();
st.pop_back();
}
if(!st.empty())tree[st.back()].sc = i;
st.push_back(i);
}
rt = st[0];
par[rt][0] = rt;
dfs(rt);
}
void init(int NN, std::vector<int> HH) {
N = NN;
arr[0] = inf;
for(int i = 0;i<N;i++)arr[i+1] = HH[i];
}
int max_towers(int L, int R, int D) {
L++,R++;
vector<pii> v;
for(int i = L;i<=R;i++){
pii rng = pii(i,i);
for(int j = i-1;j>=1;j--){
if(arr[j]>=arr[i]+D)break;
rng.fs = j;
}
for(int j = i+1;j<=N;j++){
if(arr[j]>=arr[i]+D)break;
rng.sc = j;
}
v.push_back(rng);
}
sort(v.rbegin(),v.rend());
int lp = N+1;
int ans = 0;
for(auto &[l,r]:v){
if(r<lp)ans++,lp = l;
}
return ans;
}
