#include "towers.h"
#include <bits/stdc++.h>
const int OO = 0;
using namespace std;
struct info {
int len[2][2];
info(int x = -1) {
len[0][0] = len[1][1] = -1e9;
len[0][1] = len[1][0] = -1e9;
if (x == 0) {
len[0][0] = 1;
}
if (x == 1) {
len[1][1] = 1;
}
}
info operator * (const info &a) const {
info res;
for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) {
res.len[i][j] = max(max(res.len[i][j], len[i][j]), a.len[i][j]);
}
for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) for (int k = 0; k < 2; k++) {
res.len[i][k] = max(res.len[i][k], len[i][j] + a.len[1 ^ j][k]);
}
return res;
}
void print() {
for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) {
cout << i << " -> " << j << ": " << len[i][j] << '\n';
}
}
};
struct node {
vector<pair<int, info>> data;
node() {
data.emplace_back(0, info());
}
void add(int tim, info i) {
data.emplace_back(tim, i);
}
info& get(int tim) {
tim = max(tim, 0);
int lo = 0, hi = (int)data.size() - 1, mid;
while (lo < hi) {
mid = (lo + hi + 1) / 2;
if (data[mid].first <= tim) lo = mid;
else hi = mid - 1;
}
return data[lo].second;
}
};
struct segtree {
int n;
int tim;
vector<node> t;
segtree() {}
segtree(int sz) {
tim = 0;
n = max(2, sz);
while (n != (n & -n)) n += (n & -n);
t.resize(2 * n, node());
}
void fix(int x) {
t[x].add(tim, t[2 * x + 1].get(tim) * t[2 * x + 2].get(tim));
}
void upd(int x, int val) {
tim++;
x += n - 1;
t[x].add(tim, info(val));
while (x) {
x = (x - 1) / 2;
fix(x);
}
}
info query(int l, int r, int T) {
if (l > r) return info();
return query(l, r, T, 0, 0, n - 1);
}
info query(int l, int r, int T, int node, int nl, int nr) {
if (nr < l || r < nl) return info();
if (l <= nl && nr <= r) return t[node].get(T);
int mid = (nl + nr) / 2;
return query(l, r, T, 2 * node + 1, nl, mid) * query(l, r, T, 2 * node + 2, mid + 1, nr);
}
};
int oldn;
vector<int> oldh;
int n;
vector<int> taken_ind;
vector<int> h;
vector<pair<int, int>> w;
segtree T;
void init(int N, std::vector<int> H) {
oldn = N;
oldh = H;
h = { H[0], H[1] };
taken_ind = { 0, 1 };
for (int i = 2; i < oldn; i++) {
if (abs(h[h.size() - 2] - h.back()) + abs(h.back() - H[i]) == abs(h[h.size() - 2] - H[i]))
h.pop_back(), taken_ind.pop_back();
h.push_back(H[i]);
taken_ind.push_back(i);
}
n = h.size();
for (int i = 0; i + 1 < h.size(); i++)
w.emplace_back(abs(h[i] - h[i + 1]), i);
if (OO) {
cout << "w:\n";
for (const auto &i : w) cout << i.first << " " << i.second << '\n';
}
sort(w.rbegin(), w.rend());
T = segtree(n);
for (auto &i : w) {
if (h[i.second] < h[i.second + 1])
T.upd(i.second, 0);
else
T.upd(i.second, 1);
}
}
int bruteforce(int l, int r, int d) {
int len = r - l + 1;
int best = 0;
for (int mask = 0; mask < (1 << len); mask++) {
vector<int> val;
for (int i = l; i <= r; i++) {
if (mask & (1 << (i - l)))
val.push_back(oldh[i]);
}
if (val.size() % 2 == 0) continue;
bool good = true;
for (int i = 0; i + 1 < val.size(); i++) {
if (i % 2 == 0 && val[i] + d > val[i + 1]) good = false;
if (i % 2 == 1 && val[i] - d < val[i + 1]) good = false;
}
if (good)
best = max(best, (int)val.size() / 2 + 1);
}
return best;
}
int max_towers(int L, int R, int D) {
// find time
int lo = -1, hi = (int)w.size() - 1, mid;
while (lo < hi) {
mid = (lo + hi + 1) / 2;
if (w[mid].first >= D) lo = mid;
else hi = mid - 1;
}
int tim = lo + 1;
// fix L, R
auto it = lower_bound(taken_ind.begin(), taken_ind.end(), L);
int LL = *it;
int l = it - taken_ind.begin();
it = prev(upper_bound(taken_ind.begin(), taken_ind.end(), R));
int RR = *it;
int r = it - taken_ind.begin();
// break into cases - and also don't forget to consider the boundaries
if (R < LL) {
// nothing in between - this is a monotonic range
return 1;
}
// there's something in between: l <= r
if (OO) {
cout << "data until now:\n";
cout << "taken_ind: ";
for (const auto &i : taken_ind) cout << i << " "; cout << '\n';
cout << "l LL " << l << " " << LL << '\n';
cout << "r RR " << r << " " << RR << '\n';
cout << "tim " << tim << '\n';
}
info q = T.query(l, r - 1, tim);
if (OO) {
cout << "from query received:\n";
q.print();
}
if (L < LL) {
// consider left boundary
info boundary = info();
if (oldh[L] + D <= oldh[LL])
boundary = info(0);
else if (oldh[L] - D >= oldh[LL])
boundary = info(1);
q = boundary * q;
}
if (RR < R) {
// consider right boundary
info boundary = info();
if (oldh[RR] + D <= oldh[R])
boundary = info(0);
else if (oldh[RR] - D >= oldh[R])
boundary = info(1);
q = q * boundary;
}
return max(1, max(q.len[0][0], q.len[0][1]) / 2 + 1);
}
