#include "towers.h"
#include<bits/stdc++.h>
using namespace std;
#define rall(s) s.rbegin(), s.rend()
#define all(s) s.begin(), s.end()
#define sz(s) (int)s.size()
#define s second
#define f first
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
vector<int> h;
int n, k, ok = 1;
const int inf = 1e9, N1 = 3e7;
pii t[N1];
void bld(int u = 1, int tl = 0, int tr = n - 1) {
if (tl == tr) {
t[u] = {tl, tl};
return;
}
int m = (tl + tr) / 2;
bld(u * 2, tl, m);
bld(u * 2 + 1, m + 1, tr);
t[u] = t[u * 2 + 1];
if (h[t[u * 2].f] > h[t[u].f]) t[u].f = t[u * 2].f;
if (h[t[u * 2].s] < h[t[u].s]) t[u].s = t[u * 2].s;
}
pii get(int l, int r, int u = 1, int tl = 0, int tr = n - 1) {
if (tl > r || tr < l) return {-1, -1};
if (tl >= l && tr <= r) return t[u];
int m = (tl + tr) / 2;
auto [x1, x2] = get(l, r, u * 2, tl, m);
auto [y1, y2] = get(l, r, u * 2 + 1, m + 1, tr);
if (x1 == -1) return {y1, y2};
if (y1 == -1) return {x1, x2};
if (h[y1] > h[x1]) x1 = y1;
if (h[y2] < h[x2]) x2 = y2;
return {x1, x2};
}
int t2[N1], vl[N1], vr[N1], cur = 1;
void upd(int l, int r, int u = 1, int tl = 1, int tr = inf) {
if (tl > r || tr < l || r < l) return;
if (tl >= l && tr <= r) {
t2[u]++;
return;
}
int m = (tl + tr) / 2;
if (!vl[u]) vl[u] = ++cur;
if (!vr[u]) vr[u] = ++cur;
upd(l, r, vl[u], tl, m);
upd(l, r, vr[u], m + 1, tr);
}
int gt(int p, int u = 1, int tl = 1, int tr = inf) {
if (tl == tr) return t2[u];
int m = (tl + + tr) / 2;
if (p <= m) {
if (vl[u]) return gt(p, vl[u], tl, m) + t2[u];
return t2[u];
}
if (vr[u]) return gt(p, vr[u], m + 1, tr) + t2[u];
return t2[u];
}
void calc(int l, int r, int mx) {
if (r < l) return;
if (l == r) {
upd(1, min(inf, mx - h[l]));
return;
}
auto [pos, ps] = get(l, r);
if (pos == l) calc(l + 1, r, mx);
else if (pos == r) calc(l, r - 1, mx);
else {
upd(h[pos] - h[ps] + 1, min(inf, mx - h[ps]));
calc(l, pos - 1, h[pos]);
calc(pos + 1, r, h[pos]);
}
}
void init(int N, vector<int> H) {
n = N, h = H;
k = n - 1;
for (int i = 1; i < n; i++) {
if (h[i] < h[i - 1]) {
k = i - 1;
break;
}
}
for (int i = 1; i < k; i++) {
if (h[i - 1] > h[i]) ok = 0;
}
for (int i = k + 1; i < n; i++) {
if (h[i - 1] < h[i]) ok = 0;
}
bld();
calc(0, n - 1, 2 * inf);
}
int f(int l, int r, int d, int mx) {
if (r < l) return 0;
if (l == r) return (h[l] <= mx);
auto [pos, ps] = get(l, r);
if (h[ps] > mx) return 0;
if (pos == l) return f(l + 1, r, d, mx);
if (pos == r) return f(l, r - 1, d, mx);
return max(1, f(l, pos - 1, d, min(mx, h[pos] - d)) + f(pos + 1, r, d, min(mx, h[pos] - d)));
}
int max_towers(int l, int r, int d) {
if (ok) {
if (k == -1) return 1;
if (k <= l || r <= k) return 1;
if (h[l] > h[k] - d || h[r] > h[k] - d) return 1;
return 2;
}
if (l == 0 && r == n - 1) {
return gt(d);
}
return f(l, r, d, inf);
}
