#include "towers.h"
#include <bits/stdc++.h>
#define uwu return
using namespace std;
#define fs first
#define sc second
#define all(x) x.begin(), x.end()
const int SIZE = 1e5 + 5, LOG_C = 19;
int sps_tbl[LOG_C][SIZE], H[SIZE];
int pos_max(int a, int b){
if(H[a] > H[b])
return a;
return b;
}
void output(long long a, bool b){
if(b)
cerr << '\n';
else
cerr << a << ' ';
return;
}
int query(int l, int r){
int lv = __lg(r - l + 1);
uwu pos_max(sps_tbl[lv][l], sps_tbl[lv][r - (1 << lv) + 1]);
}
bool is_leaf[SIZE];
int pref[SIZE];
vector <int> graph[SIZE];
int build_cartesian(int l, int r){
if (l == r){
is_leaf[l] = 1;
return l;
}
int rt = query(l, r);
if(rt == l)
graph[rt].push_back(build_cartesian(rt + 1, r));
else if(rt == r)
graph[rt].push_back(build_cartesian(l, rt - 1));
else{
graph[rt].push_back(build_cartesian(rt + 1, r));
graph[rt].push_back(build_cartesian(l, rt - 1));
}
return rt;
}
void init(int N, vector<int> _H) {
for (int i = 0; i < N; i++){
sps_tbl[0][i] = i;
H[i] = _H[i];
}
for (int lv = 1; lv < LOG_C; lv++){
for (int i = 0; i < N - (1 << lv) + 1; i++){
sps_tbl[lv][i] = pos_max(sps_tbl[lv - 1][i], sps_tbl[lv - 1][i + (1 << (lv - 1))]);
}
}
build_cartesian(0, N - 1);
for (int i = 1; i <= N; i++){
pref[i] = pref[i - 1] + is_leaf[i - 1];
}
uwu;
}
map <int, int> dp[SIZE];
void do_stuff(int nd, int D){
dp[nd][H[nd]] = 1;
for(auto i:graph[nd]){
do_stuff(i, D);
if(dp[i].size() > dp[nd].size())
swap(dp[i], dp[nd]);
int small_max = 0, big_max = 0;
for (auto it = dp[i].begin(); it != dp[i].end(); it = dp[i].erase(it)){
auto j = *it;
if (j.fs <= H[nd] - D)
small_max = max(small_max, j.sc);
else
break;
}
for (auto it = dp[nd].begin(); it != dp[nd].end(); it = dp[nd].erase(it)){
auto j = *it;
if (j.fs <= H[nd] - D)
big_max = max(big_max, j.sc);
else
break;
}
dp[nd][H[nd] - D] = max(dp[nd][H[nd] - D], small_max + big_max);
for(auto j:dp[i]){
dp[nd][j.fs] = max(dp[nd][j.fs], j.sc);
}
}
return;
}
int max_towers(int L, int R, int D) {
if(R == L)
uwu 1;
int sum = pref[R + 1] - pref[L];
if(!is_leaf[L]){
if(graph[L].size() == 1 && graph[L][0] < L)
sum++;
}
if(!is_leaf[R]){
if(graph[R].size() == 1 && graph[R][0] > R)
sum++;
}
return sum;
}
