#include "towers.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
namespace solve{
int N; vector<int> H;
map<int, int> ans;
void init(){
set<pair<int, int>> T;
set<pair<int, pair<int, int>>> S;
vector<bool> active(N, true);
for(int i = 0; i < N; i++){
if(i > 0 && i < N - 1 && ((H[i - 1] <= H[i] && H[i] <= H[i + 1]) || (H[i - 1] >= H[i] && H[i] >= H[i + 1]))) {
active[i] = false;
continue;
}
T.insert({i, H[i]});
}
if (T.size() >= 2 && (T.begin())->se > next(T.begin())->se) {
active[T.begin()->fi] = false;
T.erase(T.begin());
}
if (T.size() >= 2 && prev(T.end())->se > prev(prev(T.end()))->se) {
active[prev(T.end())->fi] = false;
T.erase(prev(T.end()));
}
/*
cout << "D = 0" << endl;
for(auto t : T){
cout << "[" << t.fi << "] => " << t.se << endl;
}
*/
ans[0] = (T.size() + 1) / 2;
for(auto t = T.begin(); t != T.end(); t++){
if(t != T.begin()) {
S.insert({abs(t->se - prev(t)->se), {t->fi, prev(t)->fi}});
}
}
vector<int> Ir;
while(S.size()){
auto [d, p] = *S.begin(); S.erase(S.begin());
Ir.push_back(d);
int x = p.fi, y = p.se;
if(!active[x] || !active[y])
continue;
active[x] = active[y] = false;
auto ptr = T.lower_bound({x, -1});
if(ptr != T.end() && ptr->fi == x)
T.erase(ptr);
ptr = T.lower_bound({y, -1});
if(ptr != T.end() && ptr->fi == y)
T.erase(ptr);
ptr = T.lower_bound({y, -1});
if (ptr != T.begin() && ptr != T.end()) {
S.insert({abs(ptr->se - prev(ptr)->se), {ptr->fi, prev(ptr)->fi}});
}
/*
cout << "D = " << d << endl;
for(auto t : T){
cout << "[" << t.fi << "] => " << t.se << endl;
}
*/
assert(T.size() % 2 == 1);
ans[d + 1] = (T.size() + 1) / 2;
}
}
int query(int L, int R, int D) {
return (--ans.upper_bound(D))->se;
}
};
void init(int N, vector<int> H) {
solve::N = N;
solve::H = H;
solve::init();
}
int max_towers(int L, int R, int D) {
return solve::query(L, R, D);
}
