#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int n, h[maxn], pref[maxn], peak_pos;
int cnt = 0;
int par[maxn], rnk[maxn];
int find_leader(int v)
{
return (v == par[v]) ? v : par[v] = find_leader(par[v]);
}
void unite(int v, int u)
{
v = find_leader(v);
u = find_leader(u);
if (v == u)
return;
if (rnk[v] < rnk[u])
swap(v, u);
rnk[v] += rnk[u];
par[u] = v;
}
int dp[maxn], bef[maxn], aft[maxn];
int tree[4 * maxn];
void build_tree(int root, int left, int right)
{
if (left == right)
{
tree[root] = h[left];
return;
}
int mid = (left + right) / 2;
build_tree(root * 2, left, mid);
build_tree(root * 2 + 1, mid + 1, right);
tree[root] = max(tree[root * 2], tree[root * 2 + 1]);
}
void update(int root, int left, int right, int pos, int val)
{
if (left == right)
{
tree[root] = val;
return;
}
int mid = (left + right) / 2;
if (pos <= mid)
update(root * 2, left, mid, pos, val);
else
update(root * 2 + 1, mid + 1, right, pos, val);
tree[root] = max(tree[root * 2], tree[root * 2 + 1]);
}
int query(int root, int left, int right, int qleft, int qright)
{
if (left > qright || right < qleft)
return 0;
if (left >= qleft && right <= qright)
return tree[root];
int mid = (left + right) / 2;
return max(query(root * 2, left, mid, qleft, qright),
query(root * 2 + 1, mid + 1, right, qleft, qright));
}
vector < int > peaks, val, block;
void init(int N, std::vector<int> H)
{
n = N;
for (int i = 0; i < n; i ++)
h[i + 1] = H[i];
for (int i = 1; i <= n; i ++)
if (h[i] > h[i - 1] && h[i] > h[i + 1])
cnt ++;
for (int i = 2; i < n; i ++)
{
pref[i] = pref[i - 1];
if (h[i] > h[i - 1] && h[i] > h[i + 1])
{
pref[i] ++, peak_pos = i;
peaks.push_back(i);
}
}
build_tree(1, 1, n);
int last = 0;
for (int i = 0; i < peaks.size(); i ++)
{
val.push_back(query(1, 1, n, last + 1, peaks[i] - 1));
///cout << val.back() << " ";
last = peaks[i];
}
val.push_back(query(1, 1, n, last + 1, n));
///cout << val.back() << " ";
///cout << endl;
for (int i = 0; i < peaks.size(); i ++)
{
block.push_back(h[peaks[i]] - max(val[i], val[i + 1]));
///cout << block.back() << endl;
}
sort(block.begin(), block.end());
}
vector < int > act[maxn];
int max_towers(int L, int R, int D)
{
L ++;
R ++;
if (L == 1 && R == n)
{
int ans = val.size();
int lf = 0, rf = (int)(block.size()) - 1;
while(lf <= rf)
{
int mf = (lf + rf) / 2;
if (block[mf] < D)
lf = mf + 1;
else
rf = mf - 1;
}
return ans - lf;
}
if (cnt == 1)
{
if (peak_pos <= L || peak_pos >= R)
return 1;
if (h[L] <= h[peak_pos] - D && h[R] <= h[peak_pos] - D)
return 2;
return 1;
}
if (D == 1)
{
int peaks = max(0, pref[R - 1] - pref[L]);
return peaks + 1;
}
for (int i = 0; i < n; i ++)
act[i].clear();
for (int i = 0; i < 4 * n; i ++)
tree[i] = 0;
h[0] = h[n + 1] = 2e9;
vector < int > st;
st.push_back(0);
for (int i = 1; i <= n; i ++)
{
int lf = 0, rf = st.size() - 1;
while(lf <= rf)
{
int mf = (lf + rf) / 2;
if (h[st[mf]] - D >= h[i])
lf = mf + 1;
else
rf = mf - 1;
}
bef[i] = st[rf];
while(!st.empty() && h[st.back()] <= h[i])
st.pop_back();
st.push_back(i);
}
st.clear();
st.push_back(n + 1);
for (int i = n; i > 0; i --)
{
int lf = 0, rf = st.size() - 1;
while(lf <= rf)
{
int mf = (lf + rf) / 2;
if (h[st[mf]] - D >= h[i])
lf = mf + 1;
else
rf = mf - 1;
}
aft[i] = st[rf];
while(!st.empty() && h[st.back()] <= h[i])
st.pop_back();
st.push_back(i);
}
int ans = 0;
for (int i = L; i <= R; i ++)
{
for (int pos : act[i])
{
update(1, 0, n - 1, pos, dp[pos]);
}
act[i].clear();
dp[i] = 1;
int left = L, right = bef[i];
if (left <= right)
{
int x = query(1, 0, n - 1, left, right) + 1;
dp[i] = x;
}
act[aft[i]].push_back(i);
ans = max(ans, dp[i]);
}
return ans;
}
