#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 1e5+10, MOD = 1e9+7;
const ll INF = 1e18+10;
const int L = 20;
struct D1 {
int sum = 0, mn = MOD, mx = -1;
D1() {}
D1(int x, int loc) {
sum = x;
if (x) mn = mx = loc;
}
friend D1 operator + (const D1& one, const D1& two) {
D1 ans;
ans.sum = one.sum + two.sum;
ans.mn = min(one.mn, two.mn);
ans.mx = max(one.mx, two.mx);
return ans;
}
};
struct T1 {
D1 d;
T1 *l = nullptr, *r = nullptr;
T1(D1 _d): d(_d) {
}
T1(T1* _l, T1* _r): l(_l), r(_r) {
d = l->d + r->d;
}
};
T1* build1(int tl, int tr, vector<int>& v) {
if (tl == tr) {
return new T1(D1(v[tl], tl));
}
else {
int tm = (tl + tr) / 2;
build1(tl, tm, v);
build1(tm+1, tr, v);
T1* ans = new T1(build1(tl, tm, v), build1(tm+1, tr, v));
return ans;
}
}
T1* upd1(T1* t, int tl, int tr, int pos, int x) {
if (tl == tr) {
return new T1(D1(x, tl));
}
int tm = (tl + tr) / 2;
if (pos <= tm)
return new T1(upd1(t->l, tl, tm, pos, x), t->r);
else
return new T1(t->l, upd1(t->r, tm+1, tr, pos, x));
}
D1 qry1(T1* t, int tl, int tr, int l, int r) {
if (r < tl || l > tr) return D1();
if (l <= tl && tr <= r) return t->d;
int tm = (tl + tr) / 2;
return qry1(t->l, tl, tm, l, r) + qry1(t->r, tm+1, tr, l, r);
}
int n, a[N], st[N][L];
vector<pair<int, int>> store;
vector<int> base;
vector<int> ord;
T1* vers[N];
void build_rmq() {
for (int i = 0; i < n; i++) st[i][0] = a[i];
for (int k = 2, l = 1; k <= n; k *= 2, l++) {
for (int i = 0; i + k <= n; i++) {
st[i][l] = max(st[i][l-1], st[i + k / 2][l-1]);
}
}
}
int qry_max(int l, int r) {
int len = r - l + 1;
int use = 31 - __builtin_clz(len);
return max(st[l][use], st[r - (1 << use) + 1][use]);
}
void init(int _n, vector<int> H) {
n = _n;
for (int i = 0; i < n; i++) {
a[i] = H[i];
}
build_rmq();
set<int> s;
for (int i = 0; i < n; i++) {
bool use = 1;
if (i && a[i-1] < a[i]) use = 0;
if (i < n-1 && a[i+1] < a[i]) use = 0;
if (use) s.insert(i);
}
base = vector<int>(s.begin(), s.end());
auto f = [&](int i) {
auto it = s.lower_bound(i); assert(*it == i);
--it;
return qry_max(*it, i) - max(a[*it], a[i]);
};
set<pair<int, int>> q;
auto get_v = [&](int x) {
return pair<int, int>{f(x), x};
};
for (auto it = next(s.begin()); it != s.end(); it++) {
q.insert(get_v(*it));
}
vector<pair<int, int>> v;
v.emplace_back(0, sz(s)); // d > 0, ans = sz(s)
while (sz(q)) {
auto [d, i] = *q.begin(); q.erase(q.begin());
v.emplace_back(d, -1); // need to update v.back().second
auto it = s.lower_bound(i); assert(*it == i);
int one = i;
int two = *prev(it);
if (next(it) != s.end()) {
q.erase(get_v(*next(it)));
}
if (prev(it) != s.begin()) {
q.erase(get_v(two));
}
if (a[one] > a[two]) {
s.erase(one);
ord.push_back(one);
it = s.lower_bound(two);
if (next(it) != s.end()) {
q.insert(get_v(*next(it)));
}
if (it != s.begin()) {
q.insert(get_v(*it));
}
} else {
s.erase(two);
ord.push_back(two);
it = s.lower_bound(one);
if (next(it) != s.end()) {
q.insert(get_v(*next(it)));
}
if (it != s.begin()) {
q.insert(get_v(*it));
}
}
v.back().second = sz(s);
}
store.push_back(v[0]);
for (int i = 1; i < sz(v); i++) {
if (v[i].first <= store.back().first) {
store.back().second = v[i].second;
} else {
store.push_back(v[i]);
}
}
vector<int> aux_base(n);
for (int x : base) aux_base[x] = 1;
vers[0] = build1(0, n-1, aux_base);
// cerr << "done\n";
for (int i = 1; i <= sz(ord); i++) {
vers[i] = upd1(vers[i-1], 0, n-1, ord[i-1], 0);
}
// cerr << "done\n";
}
bool has[N];
int max_towers(int l, int r, int d) {
// find the last thing < d
int idx = lower_bound(store.begin(), store.end(), pair<int, int>{d, -1}) - store.begin() - 1;
int gone = sz(base) - store[idx].second;
D1 dd = qry1(vers[gone], 0, n-1, l, r);
int ans = dd.sum;
int first = dd.mn, last = dd.mx;
/*
memset(has, 0, sizeof(has));
for (int x : base) has[x] = 1;
for (int i = 0; i < gone; i++) has[ord[i]] = 0;
int ans = 0;
int first = n, last = -1;
for (int i = l; i <= r; i++) {
ans += has[i];
if (has[i]) {
first = min(first, i);
last = max(last, i);
}
}
// cerr << ans << ' ' << ' ' << first << ' ' << last << endl;
*/
if (ans == 0) {
int mx = qry_max(l, r);
return max(1, (mx - d >= a[l]) + (mx - d >= a[r]));
}
bool one = 0, two = 0;
for (int i = l; i < first; i++) {
int x = qry_max(i, first);
if (a[i] <= x - d && x - d >= a[first]) {
one = 1;
break;
}
}
for (int i = last+1; i <= r; i++) {
int x = qry_max(last, i);
if (a[i] <= x - d && x - d >= a[last]) {
two = 1;
break;
}
}
ans += one;
ans += two;
return ans;
}
