#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
template <typename T, size_t L>
struct segtree_max
{
T t[L << 1];
void update(size_t i, T x)
{
i += L;
t[i] = max(t[i], x);
while (i >>= 1)
t[i] = max(t[i << 1], t[i << 1 | 1]);
}
T range_max(size_t i, size_t j)
{
i += L, j += L;
T x = numeric_limits<T>::min();
while (i <= j)
{
if (i & 1)
x = max(x, t[i++]);
if (!(j & 1))
x = max(x, t[j--]);
i >>= 1;
j >>= 1;
}
return x;
}
void reset() { memset(t, 0, sizeof t); }
};
constexpr size_t N = 100000;
int subtask, h[N], coords[3 * N];
size_t n, peak_pos;
segtree_max<int64_t, 3 * N> towers, intermediate;
void init(int n_, vector<int> h_)
{
n = n_;
copy(h_.begin(), h_.end(), h);
bool increasing = 1;
subtask = 1;
for (size_t i = 0; i + 1 < n; ++i)
{
if (h[i] < h[i + 1] && !increasing)
{
subtask = 2;
break;
}
if (h[i] > h[i + 1])
increasing = 0;
}
if (subtask == 1)
{
while (peak_pos + 1 < n && h[peak_pos + 1] > h[peak_pos])
++peak_pos;
return;
}
else
{
subtask = 3;
}
}
size_t ind(int64_t coord) { return lower_bound(coords, coords + 3 * n, coord) - coords; }
int max_towers(int l, int r, int d)
{
if (subtask == 1)
{
if (l >= peak_pos || r <= peak_pos)
return 1;
return (h[peak_pos] >= h[l] + d && h[peak_pos] >= h[r] + d) + 1;
}
else
{
memcpy(coords, h, sizeof h);
for (size_t i = 0; i < n; ++i)
coords[n + i] = coords[i] + d, coords[2 * n + i] = coords[i] - d;
sort(coords, coords + 3 * n);
towers.reset();
intermediate.reset();
towers.update(ind(h[l]), 1);
int ans = 1;
for (size_t i = l + 1; i <= r; ++i)
{
// as intermediate
int64_t v = towers.range_max(0, ind(h[i] - d));
intermediate.update(ind(h[i]), v);
// as tower
v = intermediate.range_max(ind(h[i] + d), 3 * n - 1) + 1;
towers.update(ind(h[i]), v);
ans = max<int>(ans, v);
}
return ans;
}
}
