#include "towers.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
namespace solve{
int N; vector<int> H;
vector<bool> active;
struct node{
int l, r, s; node *ll, *rr;
node(int l, int r, int s = 1) : l(l), r(r), s(s), ll(0), rr(0) {};
node(node *ll, node *rr) : l(ll->l), r(rr->r), s(ll->s + rr->s), ll(ll), rr(rr) {};
};
map<int, node*> ans;
node* build(int l, int r){
node* p = new node(l, r);
if (l != r) {
int m = (l + r) / 2;
p->ll = build(l, m);
p->rr = build(m + 1, r);
p->s = p->ll->s + p->rr->s;
} else {
p->s = active[l];
}
return p;
}
node* update(node* root, int p, int v){
if(root->l == root->r)
return new node(root->l, root->r, v);
if(p <= root->ll->r){
node *x = update(root->ll, p, v);
node *y = root->rr;
return new node(x, y);
}else{
node *x = root->ll;
node *y = update(root->rr, p, v);
return new node(x, y);
}
}
void crawl(node* v, bool ini = true){
if(v == nullptr)
return;
if(v->ll || v->rr) {
crawl(v->ll, false);
crawl(v->rr, false);
} else {
cout << v->s << ' ';
}
if (ini) {
cout << endl;
}
}
int query(node* v, int l, int r){
if(v->r < l || r < v->l)
return 0;
if(l <= v->l && v->r <= r)
return v->s;
int x = query(v->ll, l, r);
int y = query(v->rr, l, r);
return x + y;
}
int kth(node* v, int k){
if(v->l == v->r)
return v->l;
if(k <= v->ll->s)
return kth(v->ll, k);
else
return kth(v->rr, k - v->ll->s);
}
int Min[20][100001], Max[20][100001];
int getMin(int l, int r){
int d = __lg(r - l + 1);
return H[Min[d][l]] < H[Min[d][r - (1 << d) + 1]] ? Min[d][l] : Min[d][r - (1 << d) + 1];
}
int getMax(int l, int r){
int d = __lg(r - l + 1);
return H[Max[d][l]] > H[Max[d][r - (1 << d) + 1]] ? Max[d][l] : Max[d][r - (1 << d) + 1];
}
void init(){
set<pair<int, int>> T;
set<pair<int, pair<int, int>>> S;
active = vector<bool>(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] = build(0, N - 1);
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}});
}
}
for(int i = 0; i < N; i++) Min[0][i] = i;
for(int j = 1; j < 20; j++) for(int i = 0; i <= N - (1 << j); i++) Min[j][i] = H[Min[j - 1][i]] < H[Min[j - 1][i + (1 << j - 1)]] ? Min[j - 1][i] : Min[j - 1][i + (1 << j - 1)];
for(int i = 0; i < N; i++) Max[0][i] = i;
for(int j = 1; j < 20; j++) for(int i = 0; i <= N - (1 << j); i++) Max[j][i] = H[Max[j - 1][i]] > H[Max[j - 1][i + (1 << j - 1)]] ? Max[j - 1][i] : Max[j - 1][i + (1 << j - 1)];
node* cur = ans[0];
while(S.size()){
auto [d, p] = *S.begin(); S.erase(S.begin());
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;
}
*/
cur = update(cur, x, 0);
cur = update(cur, y, 0);
ans[d + 1] = cur;
}
}
int query(int L, int R, int D) {
node *root = (--ans.upper_bound(D))->se;
int s_L = query(root, 0, L - 1);
int s = query(root, L, R);
if (s == 0) return 1;
if (s == 1) {
int M = kth(root, s_L + 1);
if(L < M && M < R){
int ML = getMin(L, M - 1);
int MR = getMin(M + 1, R);
if(H[M] >= H[ML] + D && H[M] >= H[MR] + D)
return 2;
}
return 1;
}
int L1 = kth(root, s_L + 1);
int L2 = kth(root, s_L + 2);
int R1 = kth(root, s_L + s);
int R2 = kth(root, s_L + s - 1);
int a = s;
if (H[L1] > H[L2]) {
--a;
if(L < L1){
int L0 = getMin(L, L1 - 1);
if(H[L1] - H[L0] >= D){
a += 2;
}
}
}
if (H[R1] > H[R2]) {
--a;
if(R > R1){
int R0 = getMin(R1 + 1, R);
if(H[R1] - H[R0] >= D){
a += 2;
}
}
}
return (a + 1) / 2;
}
};
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);
}
