// Fuck It We BALL
#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
#define chmax(a, b) a = max(a, b)
#define pb push_back
#define LC (v<<1)
#define RC (LC|1)
#define mid ((l+r) / 2)
const int mxn = 1e5 + 4;
int n;
int h[mxn];
struct MinRangeSeg {
struct Node {
int idx, val;
Node() {}
Node(int idx_, int val_): idx(idx_), val(val_) {}
};
int n;
vector<Node> t;
MinRangeSeg(int n_): n(n_), t(4*n_ + 16) {}
void pull(int v) {
t[v] = t[LC];
if (t[v].val > t[RC].val) t[v] = t[RC];
}
void set_val(int i, int x, int v, int l, int r) {
if (r-l == 1) {
t[v] = Node(i, x);
return;
}
i<mid ? set_val(i,x, LC, l, mid) : set_val(i,x, RC, mid, r);
pull(v);
}
void set_val(int i, int x) {
set_val(i,x, 1, 0, n);
}
Node get_min(int s, int e, int v, int l, int r) {
if (s<=l && r<=e) return t[v];
if (e <= mid) return get_min(s,e, LC, l, mid);
if (s >= mid) return get_min(s,e, RC, mid, r);
Node L = get_min(s,e, LC, l, mid);
Node R = get_min(s,e, RC, mid, r);
return L.val < R.val ? L : R;
}
Node get_min(int s, int e) {
return get_min(s, e, 1, 0, n);
}
} seg_min_h(mxn);
struct MaxRangeSeg {
struct Node {
int idx, val;
Node() {}
Node(int idx_, int val_): idx(idx_), val(val_) {}
};
int n;
vector<Node> t;
MaxRangeSeg(int n_): n(n_), t(4*n_ + 16) {}
void pull(int v) {
t[v] = t[LC];
if (t[v].val < t[RC].val) t[v] = t[RC];
}
void set_val(int i, int x, int v, int l, int r) {
if (r-l == 1) {
t[v] = Node(i, x);
return;
}
i<mid ? set_val(i,x, LC, l, mid) : set_val(i,x, RC, mid, r);
pull(v);
}
void set_val(int i, int x) {
set_val(i,x, 1, 0, n);
}
Node get_max(int s, int e, int v, int l, int r) {
if (s<=l && r<=e) return t[v];
if (e <= mid) return get_max(s,e, LC, l, mid);
if (s >= mid) return get_max(s,e, RC, mid, r);
Node L = get_max(s,e, LC, l, mid);
Node R = get_max(s,e, RC, mid, r);
return L.val > R.val ? L : R;
}
Node get_max(int s, int e) {
return get_max(s, e, 1, 0, n);
}
} seg_max_h(mxn);
void init(int N, std::vector<int> H) {
n = N;
for (int i=0; i<n; i++) h[i+1] = H[i];
for (int i=1; i<=n; i++) seg_min_h.set_val(i, h[i]);
for (int i=1; i<=n; i++) seg_max_h.set_val(i, h[i]);
}
int prv[mxn], nxt[mxn];
void prep(int d) {
for (int i=1; i<=n; i++) {
int l = 0, r = i;
while (r-l > 1) {
h[i] <= seg_max_h.get_max(mid, i).val - d ? l = mid : r = mid;
}
prv[i] = l;
}
for (int i=1; i<=n; i++) {
int l = i+1, r = n+1;
while (r-l > 1) {
h[i] <= seg_max_h.get_max(i+1, mid+1).val - d ? r = mid : l = mid;
}
nxt[i] = r;
}
for (int i=1; i<=n; i++) {
for (int j = i-1; j>=1; j--) if (h[i] <= h[j]-d) {
// cout << prv[i] << " correct = " << j << endl;
// assert(prv[i]==j);
break;
}
}
for (int i=1; i<=n; i++) {
for (int j = i+1; j<=n; j++) if (h[i] <= h[j]-d) {
// cout << nxt[i] << " correct = " << j << endl;
// assert(nxt[i]==j);
break;
}
}
}
bool DONE = false;
int max_towers(int L, int R, int D) {
L++; R++;
if (!DONE) {
prep(D);
// DONE = true;
}
return 0;
}
