#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
#define inf 0x3F3F3F3F
const int MXN = 1e5 + 5;
const int LOG = 17;
struct DATA
{
int l = -1, r = -1, sum = 0;
};
int n;
vector<int> arr;
vector<int> prv, nxt;
int mx[LOG][MXN];
int LG[MXN];
int d[MXN];
vector<int> mpd;
vector<int> q[MXN];
int nd, root[MXN];
DATA st[MXN * (LOG + 4)];
array<int, 4> st1[MXN << 2];
array<int, 4> combine(array<int, 4> x, array<int, 4> y)
{
return {min(x[0], y[0]), max(x[1], y[1]), max({x[2], y[2], y[1] - x[0]}), max({x[3], y[3], x[1] - y[0]})};
}
void build(int l, int r, int x)
{
if (l == r)
{
st1[x] = {arr[l], arr[l], 0, 0};
return;
}
int mid = (l + r) >> 1;
build(l, mid, 2*x);
build(mid + 1, r, 2*x + 1);
st1[x] = combine(st1[2*x], st1[2*x + 1]);
}
array<int, 4> getd(int l, int r, int x, int lx, int rx)
{
if (l > rx || r < lx) return {inf, -inf, 0, 0};
if (l >= lx && r <= rx) return st1[x];
int mid = (l + r) >> 1;
return combine(getd(l, mid, 2*x, lx, rx), getd(mid + 1, r, 2*x + 1, lx, rx));
}
int build(int l, int r)
{
int nw = nd++;
if (l == r)
{
st[nw].sum = 1;
return nw;
}
int mid = (l + r) >> 1;
st[nw].l = build(l, mid);
st[nw].r = build(mid + 1, r);
st[nw].sum = st[st[nw].l].sum + st[st[nw].r].sum;
return nw;
}
int upd(int l, int r, int x, int ind)
{
int nw = nd++;
st[nw] = st[x];
if (l == r)
{
st[nw].sum = 0;
return nw;
}
int mid = (l + r) >> 1;
if (ind <= mid) st[nw].l = upd(l, mid, st[x].l, ind);
else st[nw].r = upd(mid + 1, r, st[x].r, ind);
st[nw].sum = st[st[nw].l].sum + st[st[nw].r].sum;
return nw;
}
int get(int l, int r, int x, int lx, int rx)
{
if (l > rx || r < lx) return 0;
if (l >= lx && r <= rx) return st[x].sum;
int mid = (l + r) >> 1;
return get(l, mid, st[x].l, lx, rx) + get(mid + 1, r, st[x].r, lx, rx);
}
int getmx(int l, int r)
{
if (l > r) return 0;
int lg = LG[r - l + 1];
return max(mx[lg][l], mx[lg][r - (1 << lg) + 1]);
}
void init(int N, vector<int> H)
{
n = N, arr = H;
prv.assign(n, -1), nxt.assign(n, n);
LG[1] = 0;
for (int i = 2; i < MXN; i++) LG[i] = LG[i >> 1] + 1;
{
vector<int> v;
for (int i = 0; i < n; i++)
{
while (!v.empty() && arr[v.back()] > arr[i]) v.pop_back();
prv[i] = (v.empty() ? -1 : v.back());
v.push_back(i);
}
}
{
vector<int> v;
for (int i = n - 1; i >= 0; i--)
{
while (!v.empty() && arr[v.back()] > arr[i]) v.pop_back();
nxt[i] = (v.empty() ? n : v.back());
v.push_back(i);
}
}
for (int i = 0; i < n; i++) mx[0][i] = arr[i];
for (int i = 1; i < LOG; i++) for (int j = 0; j + (1 << i) - 1 < n; j++) mx[i][j] = max(mx[i - 1][j], mx[i - 1][j + (1 << (i - 1))]);
mpd = {0};
for (int i = 0; i < n; i++)
{
d[i] = min(getmx(prv[i] + 1, i - 1), getmx(i + 1, nxt[i] - 1)) - arr[i];
d[i] = max(0, d[i]);
mpd.push_back(d[i] + 1);
}
sort(mpd.begin(), mpd.end());
mpd.resize(unique(mpd.begin(), mpd.end()) - mpd.begin());
for (int i = 0; i < n; i++)
{
int ind = lower_bound(mpd.begin(), mpd.end(), d[i] + 1) - mpd.begin();
q[ind].push_back(i);
}
root[0] = build(0, n - 1);
for (int i = 1; i < mpd.size(); i++)
{
root[i] = root[i - 1];
for (int &j : q[i]) root[i] = upd(0, n - 1, root[i], j);
}
build(0, n - 1, 1);
}
int max_towers(int L, int R, int D)
{
int ind = upper_bound(mpd.begin(), mpd.end(), D) - mpd.begin() - 1;
int st = -1, en = -1;
{
int lx = L, rx = R + 1;
while (lx < rx)
{
int mid = (lx + rx) >> 1;
if (getd(0, n - 1, 1, L, mid)[2] >= D) rx = mid;
else lx = mid + 1;
}
if (lx == R + 1) return 1;
st = lx;
}
{
int lx = L - 1, rx = R;
while (lx < rx)
{
int mid = (lx + rx + 1) >> 1;
if (getd(0, n - 1, 1, mid, R)[3] >= D) lx = mid;
else rx = mid - 1;
}
if (lx == L - 1) return 1;
en = lx;
}
if (st > en) return 1;
int res = 2 + get(0, n - 1, root[ind], st + 1, en - 1);
return res;
}
