#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXK = 20;
using idata = vector<int>;
using igrid = vector<idata>;
idata heights;
int nbTowers;
void init(int N, idata H) {
nbTowers = N;
heights = H;
}
int D0 = -1;
idata jumps;
igrid jumps_2k;
igrid sum_2k;
struct MContainer {
set<pair<int, int>> m;
void append (int node, int height) {
m.insert({ height, node });
auto it = m.find({ height, node });
while (it != m.begin()) {
it --;
m.erase(*it);
it = m.find({ height, node });
}
}
int query (int height) { // find the first node greater
auto it = m.upper_bound({ height, - 1 });
if (it == m.end()) return -1;
return (*it).second;
}
};
int toMiddle (int i) {
if (i == -1) return -1;
return 2 * i + 1;
}
int toNormal (int i) {
if (i == -1) return -1;
return 2 * i;
}
void init (int D) {
// node 2i represents node i as a normal node
// node 2i + 1 represents node i as a middle node
jumps.clear();
jumps.resize(2 * nbTowers, - 1);
jumps_2k.clear();
jumps_2k.resize(2 * nbTowers, idata(MAXK, -1));
sum_2k.clear();
sum_2k.resize(2 * nbTowers, idata(MAXK, 0));
D0 = D;
MContainer container;
MContainer inverted;
for (int i = nbTowers - 1; i >= 0; i --) {
int lnt_mid = container.query( heights[i] + D );
int lnt_lnt = inverted .query( - heights[i] );
int mid_mid = container.query( heights[i] );
int mid_lnt = inverted .query( - heights[i] + D );
jumps[toNormal(i)] = toMiddle(lnt_mid);
if (lnt_mid == -1 || (lnt_lnt != -1 && lnt_lnt < lnt_mid))
jumps[toNormal(i)] = toNormal(lnt_lnt);
jumps[toMiddle(i)] = toNormal(mid_lnt);
if (mid_lnt == -1 || (mid_mid != -1 && mid_mid < mid_lnt))
jumps[toMiddle(i)] = toMiddle(mid_mid);
container.append(i, heights[i]);
inverted.append(i, -heights[i]);
}
for (int i = 0; i < 2 * nbTowers; i ++) {
jumps_2k[i][0] = jumps[i];
if (jumps[i] != -1 && (i & 1) == 1 && (jumps[i] & 1) == 0)
sum_2k[i][0] = 1;
}
for (int k = 0; k + 1 < MAXK; k ++) {
for (int i = 0; i < 2 * nbTowers; i ++) {
sum_2k[i][k + 1] = sum_2k[i][k];
if (jumps_2k[i][k] == -1) continue ;
sum_2k[i][k + 1] += sum_2k[jumps_2k[i][k]][k];
jumps_2k[i][k + 1] = jumps_2k[jumps_2k[i][k]][k];
}
}
}
int find (int node, int jump) {
for (int i = 0; i < MAXK; i ++) {
if ((1 << i) & jump) {
node = jumps_2k[node][i];
if (node == -1) return -1;
}
}
return node;
}
int jump (int node, int max) {
int a = 0;
int b = 2 * nbTowers;
int s = toNormal(node);
max = toMiddle(max);
while (b - a > 1) {
int c = (a + b) >> 1;
int j = find(s, c);
if (j == -1 || j > max) b = c;
else a = c;
}
if (find(s, a) & 1) a --;
int jump_count = a;
int res = 0;
for (int i = 0; i < MAXK; i ++) {
if ((1 << i) & jump_count) {
res += sum_2k[s][i];
s = jumps_2k[s][i];
}
}
return 1 + res;
}
int max_towers(int L, int R, int D) {
if (D != D0) {
init(D);
}
return jump(L, R);
}
