#include <bits/stdc++.h>
#include "towers.h"
using namespace std;
const int INF = INT_MAX;
class Orthogonal {
int offset;
vector <vector <int>> tour;
public:
Orthogonal(vector <int> vals) {
for (offset = 1; offset < vals.size(); offset *= 2);
tour.resize(2 * offset);
for (int i = 1; i < vals.size(); i++)
tour[i + offset].push_back(vals[i]);
for (int i = offset - 1; i; i--) {
tour[i].resize(tour[2 * i].size() + tour[2 * i + 1].size());
merge(tour[2 * i].begin(), tour[2 * i].end(), tour[2 * i + 1].begin(), tour[2 * i + 1].end(), tour[i].begin());
}
}
Orthogonal() {}
int query(int x, int lo, int hi, int from, int to, int val) {
if (lo >= to || hi <= from)
return 0;
if (lo >= from && hi <= to)
return lower_bound(tour[x].begin(), tour[x].end(), val) - tour[x].begin();
int mid = (lo + hi) / 2;
return query(2 * x, lo, mid, from, to, val) + query(2 * x + 1, mid, hi, from, to, val);
}
int query(int from, int to, int val) {
return query(1, 0, offset, from, to, val);
}
};
int N, lg;
vector <int> H;
vector <int> ex;
vector <int> lb, ub;
vector <vector <int>> mini;
vector <vector <int>> lft, rig;
Orthogonal count_lb, count_ub;
int query(int from, int to) {
if (from >= to)
return INF;
int tmp = ex[to - from];
return min(mini[from][tmp], mini[to - (1 << tmp)][tmp]);
}
void init_sparse() {
mini.resize(N + 1, vector <int> (lg + 1));
for (int i = 1; i <= N; i++)
mini[i][0] = H[i];
for (int j = 1; j <= lg; j++)
for (int i = 1; i <= N; i++)
mini[i][j] = min(mini[i][j - 1], i + (1 << j - 1) > N ? INF : mini[i + (1 << j - 1)][j - 1]);
ex.resize(N + 1);
for (int i = 2; i <= N; i++)
ex[i] = ex[i / 2] + 1;
}
void init_lft_rig() {
lft.resize(N + 2, vector <int> (lg + 1));
rig.resize(N + 2, vector <int> (lg + 1));
stack <int> s;
s.push(0);
for (int i = 1; i <= N; i++) {
while (H[s.top()] < H[i])
s.pop();
lft[i][0] = s.top();
s.push(i);
}
s = stack <int> ();
s.push(N + 1);
for (int i = N; i; i--) {
while (H[s.top()] < H[i])
s.pop();
rig[i][0] = s.top();
s.push(i);
}
rig[N + 1] = vector <int> (lg + 1, N + 1);
for (int j = 1; j <= lg; j++)
for (int i = 1; i <= N; i++) {
lft[i][j] = lft[lft[i][j - 1]][j - 1];
rig[i][j] = rig[rig[i][j - 1]][j - 1];
}
}
void init_lb_ub() {
lb.resize(N + 1);
ub.resize(N + 1);
for (int i = 1; i <= N; i++) {
int tmp = query(lft[i][0] + 1, rig[i][0]);
lb[i] = H[i] - tmp;
ub[i] = min(H[lft[i][0]], H[rig[i][0]]) - tmp;
}
count_lb = Orthogonal(lb);
count_ub = Orthogonal(ub);
}
void init(int n, vector <int> h) {
N = n;
H.resize(N + 2);
H[0] = H[N + 1] = INF;
for (int i = 1; i <= N; i++)
H[i] = h[i - 1];
while (1 << lg < N)
lg++;
init_sparse();
init_lft_rig();
init_lb_ub();
}
int max_towers(int l, int r, int d) {
l += 1;
r += 1;
int smaller_lb = count_lb.query(l, r + 1, d);
int smaller_ub = count_ub.query(l, r + 1, d);
auto binary = [&](int x, const function <bool(int)> &check, const vector <vector <int>> &anc) -> pair <int, int> {
if (!check(x))
return {0, x};
int res = 0;
for (int i = lg; i >= 0; i--)
if (check(anc[x][i])) {
x = anc[x][i];
res |= 1 << i;
}
return {res + 1, anc[x][0]};
};
auto lb_lft_plus = [&](int node) {
return rig[node][0] <= r && H[node] - query(l, rig[node][0]) < d;
};
auto lb_rig_plus = [&](int node) {
return lft[node][0] >= l && H[node] - query(lft[node][0] + 1, r + 1) < d;
};
auto lb_lft_minus = [&](int node) {
return rig[node][0] <= r && lb[node] < d;
};
auto lb_rig_minus = [&](int node) {
return lft[node][0] >= l && lb[node] < d;
};
auto ub_lft_plus = [&](int node) {
return rig[node][0] <= r && H[rig[node][0]] - query(l, rig[node][0]) < d;
};
auto ub_rig_plus = [&](int node) {
return lft[node][0] >= l && H[lft[node][0]] - query(lft[node][0] + 1, r + 1) < d;
};
auto ub_lft_minus = [&](int node) {
return rig[node][0] <= r && ub[node] < d;
};
auto ub_rig_minus = [&](int node) {
return lft[node][0] >= l && ub[node] < d;
};
auto check_mx = [&](int node) {
return rig[node][0] <= r;
};
smaller_lb += binary(l, lb_lft_plus, rig).first + binary(r, lb_rig_plus, lft).first - binary(l, lb_lft_minus, rig).first - binary(r, lb_rig_minus, lft).first;
smaller_ub += binary(l, ub_lft_plus, rig).first + binary(r, ub_rig_plus, lft).first - binary(l, ub_lft_minus, rig).first - binary(r, ub_rig_minus, lft).first;
int arg_max = binary(l, check_mx, rig).second;
smaller_lb -= lb[arg_max] < d;
smaller_lb += H[arg_max] - query(l, r + 1) < d;
smaller_ub -= ub[arg_max] < d;
return smaller_lb - smaller_ub;
}
