#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
typedef array<int, 2> pii;
const int MAXN = 1e5;
const int inf = 1e9;
int height[MAXN];
int n;
class path {
public:
bool tp; // tp = 0 is >= 2, tp = 1 is single
pii minmax; // tp = 1
pii lft; // out in, tp = 0
pii rt; // out in, tp = 0
int len; // both
bool par; // 0 is low, 1 is high, tp = 0
int d;
path() {}
path(int i) {
d = 0;
tp = 1;
minmax = pii{height[i], height[i]};
len = 1;
par = 0;
}
void reverse() {
swap(lft, rt);
par ^= (len&1)^1;
}
path(path &l, path &r, int d) : d(d) {
if (l.tp && r.tp) {
if (l.minmax[1] >= r.minmax[0]+d) {
lft = pii{l.minmax[1], r.minmax[0]};
rt = pii{r.minmax[0], l.minmax[1]};
len = 2;
par = 1;
tp = 0;
return;
}
if (l.minmax[0] <= r.minmax[1]-d) {
lft = pii{l.minmax[0], r.minmax[1]};
rt = pii{r.minmax[1], l.minmax[0]};
len = 2;
par = 0;
tp = 0;
return;
}
tp = 1;
minmax = pii{min(l.minmax[0], r.minmax[0]), max(l.minmax[1], r.minmax[1])};
len = 1;
return;
}
tp = 0;
bool rev = 0;
if (l.tp && !r.tp) {
rev = 1;
l.reverse();
r.reverse();
swap(l, r);
}
if (!l.tp && r.tp) {
bool rhigh = l.par^(l.len&1)^1; // 0 is mn, 1 is high
if (rhigh && l.rt[0] >= r.minmax[0]+d) {
lft = l.lft;
rt = pii{r.minmax[0], l.rt[0]};
par = l.par;
len = l.len+1;
}
else if (!rhigh && l.rt[0]+d <= r.minmax[1]) {
lft = l.lft;
rt = pii{r.minmax[1], l.rt[0]};
par = l.par;
len = l.len+1;
}
else if (rhigh && l.rt[0] < r.minmax[1]) {
rt = pii{r.minmax[1], l.rt[1]};
par = l.par;
len = l.len;
if (len > 2) lft = l.lft;
else lft = pii{l.rt[1], r.minmax[1]};
}
else if (!rhigh && l.rt[0] > r.minmax[0]) {
rt = pii{r.minmax[0], l.rt[1]};
par = l.par;
len = l.len;
if (len > 2) lft = l.lft;
else lft = pii{l.rt[1], r.minmax[0]};
}
else {
rt = l.rt;
lft = l.lft;
len = l.len;
par = l.par;
}
if (rev) {
swap(l, r);
l.reverse();
r.reverse();
reverse();
}
return;
}
par = l.par;
bool lhigh = l.par^(l.len&1)^1;
bool rhigh = r.par;
if (lhigh != rhigh) {
if ((lhigh && l.rt[0] >= d+r.lft[0]) || (!lhigh && l.rt[0]+d <= r.lft[0])) {
lft = l.lft;
rt = r.rt;
len = l.len+r.len;
return;
}
len = l.len+r.len-2;
if (l.len > 2) lft = l.lft;
else lft = pii{l.rt[1], r.lft[1]};
if (r.len > 2) rt = r.rt;
else rt = pii{r.lft[1], l.rt[1]};
return;
}
len = l.len+r.len-1;
if ((lhigh && l.rt[0] > r.lft[0]) || (!lhigh && l.rt[0] < r.lft[0])) {
lft = l.lft;
if (r.len > 2) rt = r.rt;
else rt = pii{r.lft[1], l.rt[0]};
return;
}
if (l.len > 2) lft = l.lft;
else lft = pii{l.rt[1], r.lft[0]};
rt = r.rt;
}
};
class stree {
public:
int lp, rp;
stree *l = nullptr;
stree *r = nullptr;
vector<path> paths;
stree(int lv, int rv) {
lp = lv;
rp = rv;
if (lp < rp) {
int mid = (lp+rp)/2;
l = new stree(lp, mid);
r = new stree(mid+1, rp);
int pos[2]; pos[0] = pos[1] = 0;
for (int i = rp-lp+1; i > 0; i--) {
bool cand;
path cur_path;
bool mx_reached = 0;
do {
if (pos[0] == l->paths.size()-1 && pos[1] == r->paths.size()-1) {
mx_reached = 1;
break;
}
cand = (r->get_cost(pos[1]) < l->get_cost(pos[0]));
pos[cand]++;
int d = max(r->get_cost(pos[1]), l->get_cost(pos[0]));
cur_path = path(l->paths[pos[0]], r->paths[pos[1]], d);
} while (cur_path.len > i); // fix inf condition
if (!mx_reached) pos[cand]--;
int mn = max(l->get_cost(pos[0]-1), r->get_cost(pos[1]-1));
int mx = min(l->get_cost(pos[0]), r->get_cost(pos[1]));
while (mx > mn+1) {
int cur = (mn+mx)/2;
cur_path = path(l->paths[pos[0]], r->paths[pos[1]], cur);
if (cur_path.len > i) mn = cur;
else mx = cur;
}
if (mx == min(l->get_cost(pos[0]), r->get_cost(pos[1]))) {
if (pos[0] == l->paths.size()-1 && pos[1] == r->paths.size()-1) break;
pos[cand]++;
}
paths.push_back(path(l->paths[pos[0]], r->paths[pos[1]], mx));
i = paths.back().len;
}
}
else {
paths.push_back(path(lp));
}
}
int get_cost(int p) {
if (p == paths.size()-1) return inf;
return paths[p+1].d;
}
path* query(int lv, int rv, int d) {
if (lp > rv || rp < lv) return nullptr;
if (lp >= lv && rp <= rv) {
int mn = 0;
int mx = paths.size();
// cerr << mn << ' ' << mx << endl;
while (mx > mn+1) {
int cur = (mn+mx)/2;
if (paths[cur].d <= d) mn = cur;
else mx = cur;
}
return &paths[mn];
}
path *lq = l->query(lv, rv, d);
path *rq = r->query(lv, rv, d);
if (lq == nullptr) return rq;
if (rq == nullptr) return lq;
return new path(*lq, *rq, d);
}
};
stree *tree;
void init(int nn, vector<int> hn) {
n = nn;
for (int i = 0; i < n; i++) height[i] = hn[i];
tree = new stree(0, n-1);
}
int max_towers(int l, int r, int d) {
path *p = tree->query(l, r, d);
return (p->len+1-p->par)/2;
}
