#include <bits/stdc++.h>
#include "towers.h"
using namespace std;
typedef long long ll;
int n, pow2;
vector<int> h;
vector<int> segMn, segMx, segPeak, segVal;
vector<vector<int>> jmp;
bool initialized;
int nxtPeak(int i, int val) {
i += pow2;
while (i) {
if (segMx[i] >= val) break;
if (i & 1) {
if ((i & (i+1)) == 0) return n;
i++;
}
i /= 2;
}
while (i < pow2) {
if (segMx[2*i] >= val) i = 2*i;
else i = 2*i+1;
}
return i-pow2;
}
int nxtVal(int i, int val) {
i += pow2;
while (i) {
if (segMn[i] <= val) break;
if (i & 1) {
if ((i & (i+1)) == 0) return n;
i++;
}
i /= 2;
}
while (i < pow2) {
if (segMn[2*i] <= val) i = 2*i;
else i = 2*i+1;
}
return i-pow2;
}
void setSegPeak(int i, int val) {
i += pow2;
segPeak[i] = val;
i /= 2;
while (i) {
segPeak[i] = min(segPeak[2*i], segPeak[2*i+1]);
i /= 2;
}
}
void setSegVal(int i, int val) {
i += pow2;
segVal[i] = val;
i /= 2;
while (i) {
segVal[i] = min(segVal[2*i], segVal[2*i+1]);
i /= 2;
}
}
int getSegPeak(int low, int high) {
low += pow2; high += pow2;
int res = n;
while (low <= high) {
if (low & 1) res = min(res, segPeak[low++]);
if (!(high & 1)) res = min(res, segPeak[high--]);
low /= 2; high /= 2;
}
return res;
}
int getSegVal(int low, int high) {
low += pow2; high += pow2;
int res = n;
while (low <= high) {
if (low & 1) res = min(res, segVal[low++]);
if (!(high & 1)) res = min(res, segVal[high--]);
low /= 2; high /= 2;
}
return res;
}
void init(int N, vector<int> H) {
n = N; h = H;
initialized = false;
pow2 = 1 << (int)ceil(log2(n));
segMn = vector<int>(2*pow2);
segMx = vector<int>(2*pow2);
for (int i = 0; i < n; i++) {
segMn[pow2+i] = h[i];
segMx[pow2+i] = h[i];
}
for (int i = pow2-1; i > 0; i--) {
segMn[i] = min(segMn[2*i], segMn[2*i+1]);
segMx[i] = max(segMx[2*i], segMx[2*i+1]);
}
}
void init2(int D) {
initialized = true;
segPeak = vector<int>(2*pow2, n);
segVal = vector<int>(2*pow2, n);
for (int i = n-2; i >= 0; i--) {
int nxtP = nxtPeak(i+1, h[i]+D);
int nxtV = nxtVal(i+1, h[i]-D);
nxtP = min(nxtP, getSegPeak(i+1, nxtP-1));
nxtV = min(nxtV, getSegVal(i+1, nxtV-1));
setSegPeak(i, nxtP);
setSegVal(i, nxtV);
}
jmp = vector<vector<int>>(n, vector<int>(20, n));
for (int i = 0; i < n; i++) {
jmp[i][0] = segVal[pow2+segPeak[pow2+i]];
}
for (int b = 1; b < 20; b++) {
for (int i = 0; i < n; i++) {
int nxt = jmp[i][b-1];
if (nxt >= n) continue;
jmp[i][b] = jmp[nxt][b-1];
}
}
}
int max_towers(int L, int R, int D) {
if (!initialized) init2(D);
int res = 1;
int cur = L;
for (int b = 20-1; b >= 0; b--) {
int nxt = jmp[cur][b];
if (nxt > R) continue;
cur = nxt;
res += 1 << b;
}
return res;
}
#ifdef TEST
#include "stub.cpp"
#endif
