#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
struct node1 {
pair<int, int> max_val, min_val;
int max_diff, min_diff;
node1(): max_val(make_pair(0, 0)), min_val(make_pair(0, 0)), max_diff(0), min_diff(0) {};
node1(pair<int, int> _max_val, pair<int, int> _min_val, int _max_diff, int _min_diff): max_val(_max_val), min_val(_min_val), max_diff(_max_diff), min_diff(_min_diff) {};
};
struct node2 {
int cnt, min_pos, max_pos;
node2 *left;
node2 *right;
node2(): cnt(0), min_pos(0), max_pos(0), left(nullptr), right(nullptr) {};
node2(int _cnt, int _min_pos, int _max_pos, node2 *_left, node2 *_right): cnt(_cnt), min_pos(_min_pos), max_pos(_max_pos), left(_left), right(_right) {};
};
const int inf = 1e9 + 20;
const int maxN = 1e5 + 20;
int H[maxN];
node1 tree1[maxN * 4];
int N;
node1 merge1(node1 left, node1 right) {
return node1(max(left.max_val, right.max_val), min(left.min_val, right.min_val), max(max(left.max_diff, right.max_diff), left.max_val.first - right.min_val.first), min(min(left.min_diff, right.min_diff), left.min_val.first - right.max_val.first));
}
node2* merge2(node2 *left, node2 *right) {
return new node2(left->cnt + right->cnt, min(left->min_pos, right->min_pos), max(left->max_pos, right->max_pos), left, right);
}
void build1(int id, int lt, int rt) {
if (lt == rt) {
tree1[id] = node1(make_pair(H[lt], lt), make_pair(H[lt], lt), 0, 0);
return;
}
int mt = (lt + rt) / 2;
build1(id * 2, lt, mt);
build1(id * 2 + 1, mt + 1, rt);
tree1[id] = merge1(tree1[id * 2], tree1[id * 2 + 1]);
}
node2* build2(int lt, int rt) {
if (lt == rt) {
return new node2(0, N + 1, 0, nullptr, nullptr);
}
int mt = (lt + rt) / 2;
return new node2(0, N + 1, 0, build2(lt, mt), build2(mt + 1, rt));
}
node2* update2(node2 *cur, int lt, int rt, int pos) {
if (lt == rt) {
return new node2(1, pos, pos, nullptr, nullptr);
}
int mt = (lt + rt) / 2;
if (pos <= mt) {
return merge2(update2(cur->left, lt, mt, pos), cur->right);
}
else {
return merge2(cur->left, update2(cur->right, mt + 1, rt, pos));
}
}
node2* get2(node2 *cur, int lt, int rt, int ql, int qr) {
if (lt == ql && rt == qr) {
return cur;
}
int mt = (lt + rt) / 2;
if (qr <= mt) {
return get2(cur->left, lt, mt, ql, qr);
}
else if (ql >= mt + 1) {
return get2(cur->right, mt + 1, rt, ql, qr);
}
else {
return merge2(get2(cur->left, lt, mt, ql, mt), get2(cur->right, mt + 1, rt, mt + 1, qr));
}
}
int _get_firstL(int id, int lt, int rt, int pos, int low) {
if (lt == rt) {
return lt - (H[lt] < low);
}
if (tree1[id].max_val.first < low) {
return lt - 1;
}
int mt = (lt + rt) / 2;
if (pos <= mt) {
return _get_firstL(id * 2, lt, mt, pos, low);
}
else {
int res = _get_firstL(id * 2 + 1, mt + 1, rt, pos, low);
return (res >= mt + 1 ? res : _get_firstL(id * 2, lt, mt, pos, low));
}
}
int _get_firstR(int id, int lt, int rt, int pos, int low) {
if (lt == rt) {
return rt + (H[rt] < low);
}
if (tree1[id].max_val.first < low) {
return rt + 1;
}
int mt = (lt + rt) / 2;
if (pos >= mt + 1) {
return _get_firstR(id * 2 + 1, mt + 1, rt, pos, low);
}
else {
int res = _get_firstR(id * 2, lt, mt, pos, low);
return (res <= mt ? res : _get_firstR(id * 2 + 1, mt + 1, rt, pos, low));
}
}
node1 get1(int id, int lt, int rt, int ql, int qr) {
if (lt == ql && rt == qr) {
return tree1[id];
}
int mt = (lt + rt) / 2;
if (qr <= mt) {
return get1(id * 2, lt, mt, ql, qr);
}
else if (ql >= mt + 1) {
return get1(id * 2 + 1, mt + 1, rt, ql, qr);
}
else {
return merge1(get1(id * 2, lt, mt, ql, mt), get1(id * 2 + 1, mt + 1, rt, mt + 1, qr));
}
}
int get_firstL(int pos, int D) {
return _get_firstL(1, 1, N, pos, H[pos] + D);
}
int get_firstR(int pos, int D) {
return _get_firstR(1, 1, N, pos, H[pos] + D);
}
bool checkL(int pos, int D, int L) {
int firstL = get_firstL(pos, D);
if (firstL <= L) {
return false;
}
auto left = get1(1, 1, N, L, firstL - 1);
auto right = get1(1, 1, N, firstL, pos);
return (left.min_diff <= -D) || (right.max_val.first - left.min_val.first >= D);
}
bool checkR(int pos, int D, int R) {
int firstR = get_firstR(pos, D);
if (firstR >= R) {
return false;
}
auto right = get1(1, 1, N, firstR + 1, R);
auto left = get1(1, 1, N, pos, firstR);
return (right.max_diff >= D) || (left.max_val.first - right.min_val.first >= D);
}
vector<int> dists;
vector<int> add;
vector<node2*> roots;
void init(int _N, vector<int> _H) {
if (_N <= 2) {
return;
}
N = _N;
for (int i = 1; i <= N; i++) {
H[i] = _H[i - 1];
}
build1(1, 1, N);
vector<int> extr;
if (H[1] < H[2]) {
extr.push_back(1);
}
for (int i = 2; i <= N - 1; i++) {
if ((H[i - 1] < H[i]) ^ (H[i] < H[i + 1])) {
extr.push_back(i);
}
}
if (H[N - 1] > H[N]) {
extr.push_back(N);
}
set<int> S(extr.begin(), extr.end());
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> Q;
for (int i = 1; i < (int)extr.size(); i++) {
Q.emplace(abs(H[extr[i - 1]] - H[extr[i]]), make_pair(extr[i - 1], extr[i]));
}
while (!Q.empty()) {
int dist = Q.top().first;
int X = Q.top().second.first;
int Y = Q.top().second.second;
Q.pop();
auto it = S.find(X);
if (it == S.end() || next(it) == S.end() || *next(it) != Y) {
continue;
}
dists.push_back(dist);
add.push_back(H[X] < H[Y] ? X : Y);
it = S.erase(it);
it = S.erase(it);
if (it != S.begin() && it != S.end()) {
int prv = *prev(it);
int nxt = *it;
Q.emplace(abs(H[prv] - H[nxt]), make_pair(prv, nxt));
}
}
dists.push_back(inf);
add.push_back(*S.begin());
roots.resize((int)dists.size() + 1);
roots.back() = build2(1, N);
for (int i = (int)roots.size() - 2; i >= 0; i--) {
roots[i] = update2(roots[i + 1], 1, N, add[i]);
}
}
int max_towers(int L, int R, int D) {
L++;
R++;
if (R - L <= 1) {
return 1;
}
node2 *range = get2(roots[lower_bound(dists.begin(), dists.end(), D) - dists.begin()], 1, N, L, R);
if (!range->cnt) {
int pos = get1(1, 1, N, L, R).min_val.second;
return 1 + (checkL(pos, D, L) || checkR(pos, D, R));
}
else {
return range->cnt + checkL(range->min_pos, D, L) + checkR(range->max_pos, D, R);
}
}
