#include "towers.h"
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int N = 2e5 + 5, inf = 1e9;
int T[20 * N][3], lc[20 * N][3], rc[20 * N][3];
int c[3], r[N][3], n, A[N], tree[4 * N][2];
vector<int> x, a, ll, rr;
vector<pair<int,int>>add[N][3];
void build(int u, int l, int r) {
if(l == r) {
tree[u][0] = l;
tree[u][1] = a[l];
return;
}
int mid = (l + r) / 2;
build(2 * u, l, mid); build(2 * u + 1, mid + 1, r);
tree[u][0] = (a[tree[2 * u][0]] < a[tree[2 * u + 1][0]] ? tree[2 * u][0] : tree[2 * u + 1][0]);
tree[u][1] = max(tree[2 * u][1], tree[2 * u + 1][1]);
}
int MX(int u, int st, int en,int l,int r,int t) {
if(l > en || r < st) return (t == 0 ? n : 0);
if(st <= l && r <= en) return tree[u][t];
int mid = (l + r) / 2;
int x = MX(2 * u, st, en, l, mid, t), y = MX(2 * u + 1, st, en, mid + 1, r, t);
if(t == 0) return (a[x] < a[y] ? x : y);
return max(x, y);
}
void build(int u, int l, int r, int t) {
T[u][t] = (t == 1 ? n : 0);
if(l == r) return;
lc[u][t] = ++c[t]; rc[u][t] = ++c[t];
build(lc[u][t], l, (l + r) / 2, t); build(rc[u][t], (l + r) / 2 + 1, r, t);
}
int merge(int a, int b, int t) {
return (t == 0 ? max(a, b) : t == 1 ? min(a, b) : a + b);
}
void upd(int u, int id, int l, int r, int t, int v) {
if(l == r) {
T[c[t]][t] = v;
return;
}
int mid = (l + r) / 2, x = c[t];
lc[x][t] = lc[u][t], rc[x][t] = rc[u][t];
if(id <= mid) lc[x][t] = ++c[t], upd(lc[u][t], id, l, mid, t, v);
else rc[x][t] = ++c[t], upd(rc[u][t], id, mid + 1, r, t, v);
T[x][t] = merge(T[lc[x][t]][t], T[rc[x][t]][t], t);
}
int get(int u, int st, int en, int l, int r, int t) {
if(l > en || r < st || l > r) return (t == 1 ? n : 0);
if(st <= l && r <= en) return T[u][t];
int mid = (l + r) / 2;
return merge(get(lc[u][t], st, en, l, mid, t), get(rc[u][t], st, en, mid + 1, r, t), t);
}
void init(int nn, std::vector<int> A) {
n = nn;
vector<int> L(n), R(n), f(n);
stack<int> st;
a = A; a.push_back(inf);
for(int i = 0; i < n; i++) {
while(st.size() && a[st.top()] > a[i]) st.pop();
L[i] = (st.size() ? st.top() : -1);
st.push(i);
}
build(1, 0, n - 1);
while(st.size()) st.pop();
for(int i = n - 1; i >= 0; i--) {
while(st.size() && a[st.top()] > a[i]) st.pop();
R[i] = (st.size() ? st.top(): n );
st.push(i);
int dl = (L[i] != -1 ? MX(1, L[i], i - 1, 0, n - 1, 1) - a[i] : inf),
dr = (R[i] != n ? MX(1, i + 1, R[i], 0, n - 1, 1) - a[i] : inf);
x.push_back(dl);
x.push_back(dr);
}
sort(x.begin(), x.end());
x.erase(unique(x.begin(), x.end()), x.end());
for(int i = 0; i < n; i++) {
int dl = (L[i] != -1 ? MX(1, L[i], i - 1, 0, n - 1, 1) - a[i] : inf),
dr = (R[i] != n ? MX(1, i + 1, R[i], 0, n - 1, 1) - a[i] : inf);
dl = lower_bound(x.begin(), x.end(), dl) - x.begin();
dr = lower_bound(x.begin(), x.end(), dr) - x.begin();
// x <= min(dl, dr)
add[min(dl, dr)][2].push_back({i, 1});
if(dl == dr) continue;
if(dl < dr) {
// x <= dr
add[dr][1].push_back({i, L[i]});
add[dl][1].push_back({i, n});
continue;
}
add[dl][0].push_back({i, R[i]});
add[dr][0].push_back({i, 0});
}
// <=
ll = L; rr = R;
for(int t = 0; t <= 2; t++) r[x.size()][t] = ++c[t], build(c[t], 0, n - 1, t);
for(int i = (int)x.size() - 1; i >= 0; i--) {
for(int t = 0; t <= 2; t++) {
r[i][t] = r[i + 1][t];
for(int j = 0; j < add[i][t].size(); j++) {
int x = ++c[t];
upd(r[i][t], add[i][t][j].f, 0, n - 1, t, add[i][t][j].s);
r[i][t] = x;
}
}
}
}
int max_towers(int L, int R, int D) {
int Dd = D;
D = lower_bound(x.begin(), x.end(), D) - x.begin();
assert(r[D][1]);
int ans = get(r[D][2], L, R, 0, n - 1, 2);
int id = MX(1, L, R, 0, n - 1, 0);
ans += (!get(r[D][2], id, id, 0, n - 1, 2));
/*
int cl = 0, cr = 0;
for(int i = id - 1; i >= L; i--) {
if(get(r[D][2], i, i, 0, n - 1, 2)) continue;
int dl = (ll[i] >= L ? MX(1, ll[i], i - 1, 0, n - 1, 1) - a[i] : inf), dr = (rr[i] != n ? MX(1, i + 1, rr[i], 0, n - 1, 1) - a[i] : inf);
if(ll[i] < L && dr >= Dd) ++cl;
}
for(int i = id + 1; i <= R; i++) {
if(get(r[D][2], i, i, 0, n - 1, 2)) continue;
int dl = (ll[i] != -1 ? MX(1, ll[i], i - 1, 0, n - 1, 1) - a[i] : inf), dr = (rr[i] <= R ? MX(1, i + 1, rr[i], 0, n - 1, 1) - a[i] : inf);
if(min(dl, dr) >= Dd) ++cr;
} */
ans += (get(r[D][1], L, id - 1, 0, n - 1, 1) < L) + (get(r[D][0], id + 1, R, 0, n - 1, 0) > R);
return ans;
}
