#include "towers.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
constexpr int INF = 1000000000;
vector<int> _heights;
void init(int N, std::vector<int> H) {
_heights = H;
}
struct PakTree {
int al, ar;
int rmax;
unique_ptr<PakTree> left, right;
PakTree(int i, int j, vector<int> &pts) : al(pts[i]), ar(pts[j]), rmax(-INF) {
if (i != j) {
int k = (j - i) / 2 + i;
left = make_unique<PakTree>(i, k, pts);
right = make_unique<PakTree>(k+1, j, pts);
}
}
void set(int i, int v) {
if (i < al || ar < i) return;
else if (left == nullptr) {
rmax = v;
} else {
left->set(i, v); right->set(i, v);
rmax = max(left->rmax, right->rmax);
}
}
int getMax(int i, int j) {
if (i <= al && ar <= j) return rmax;
else if (ar < i || j < al) return -INF;
else return max(left->getMax(i, j), right->getMax(i, j));
}
void _debug() {
if (left == nullptr) {
printf("(%d, %d) ", al, rmax);
} else {
left->_debug(); right->_debug();
}
}
void debug(const char *label) {
printf("%s: ", label);
_debug();
printf("\n");
}
};
int max_towers(int L, int R, int D) {
vector<int> heights(begin(_heights) + L, begin(_heights) + R + 1);
vector<int> sheights = heights;
int N = heights.size();
sort(begin(sheights), end(sheights));
PakTree lastUp(0, N - 1, sheights), lastDown(0, N - 1, sheights);
for (int v : heights) {
int ldPrev = lastDown.getMax(-INF, v - D);
int luPrev = lastUp.getMax(v + D, INF);
lastUp.set(v, ldPrev + 1);
lastDown.set(v, max(luPrev + 1, 1)); // start is always a lastDown
/*
lastUp.debug("lastUp");
lastDown.debug("lastDown");
*/
}
return lastDown.getMax(-INF, INF) / 2 + 1;
}
