#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
template <class T> using vt = vector<T>;
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)
struct ST {
int N;
vt<int> st;
void init(const int n) {
N = n;
st.resize(n << 1);
}
void update(int i, const int v) {
st[i += N] = v;
while (i >>= 1)
st[i] = min(st[i<<1], st[i<<1|1]);
}
int query(int l, int r) {
int ret = INT_MAX;
for (l += N, r += N+1; l < r; l >>= 1, r >>= 1) {
if (l & 1)
ret = min(ret, st[l++]);
if (r & 1)
ret = min(ret, st[--r]);
}
return ret;
}
} st, st2;
constexpr int mxN = 100005, LOG = 16;
int N, K, D, lift[mxN][LOG+1];
vt<int> H;
int max_towers(int l, int r, int d) {
if (K < 0) {
if (d != D) {
D = d;
vt<int> L(N), R(N), stk = {-1};
FOR(i, 0, N-1) {
while (size(stk) > 1 && H[stk.back()] < H[i])
stk.pop_back();
int lo = 0, hi = size(stk) - 1;
while (lo < hi) {
const int mid = lo + hi + 1 >> 1;
if (H[i] + D <= H[stk[mid]])
lo = mid;
else
hi = mid - 1;
}
L[i] = stk[lo];
stk.push_back(i);
}
stk = {N};
ROF(i, N-1, 0) {
while (size(stk) > 1 && H[i] > H[stk.back()])
stk.pop_back();
int lo = 0, hi = size(stk) - 1;
while (lo < hi) {
const int mid = lo + hi + 1 >> 1;
if (H[i] + D <= H[stk[mid]])
lo = mid;
else
hi = mid - 1;
}
R[i] = stk[lo];
stk.push_back(i);
}
vt<int> sweep(N, N);
st.init(N);
st2.init(N);
FOR(i, 0, N-1) {
st.update(i, R[i]);
st2.update(i, -L[i]);
if (L[i] >= 0)
sweep[L[i]] = min(sweep[L[i]], R[i]);
}
fill(lift[N], lift[N] + LOG + 1, N);
ROF(i, N-1, 0) {
if (i+1 < N)
sweep[i] = min(sweep[i], sweep[i+1]);
lift[i][0] = sweep[i];
FOR(j, 1, LOG)
lift[i][j] = lift[lift[i][j-1]][j-1];
}
}
int i = st.query(l, r), ret = 1;
ROF(j, LOG, 0)
if (lift[i][j] <= r) {
i = lift[i][j];
ret += 1 << j;
}
return ret + (-st2.query(i, r) >= i);
}
if (K >= 0) {
if (l >= K || r <= K)
return 1;
int a, b;
{
int lo = l-1, hi = K-1;
while (lo < hi) {
const int mid = lo + hi + 1 >> 1;
if (H[mid] + d <= H[K])
lo = mid;
else
hi = mid - 1;
}
a = lo;
}
{
int lo = K+1, hi = r+1;
while (lo < hi) {
const int mid = lo + hi >> 1;
if (H[mid] + d <= H[K])
hi = mid;
else
lo = mid + 1;
}
b = lo;
}
return (a-l+1) + (r-b+1);
}
}
void init(int _N, vt<int> _H) {
N = _N, H = _H;
K = max_element(all(H)) - H.begin();
bool sub1 = true;
FOR(i, 0, K-1)
sub1 &= H[i] < H[i+1];
FOR(i, K, N-2)
sub1 &= H[i] > H[i+1];
if (!sub1)
K = -1;
}
