#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e5 + 5, maxN = 4e5 + 5, INF = 1e15;
int n;
int a[maxn], sum[maxn];
pair<int,int> seg[maxN][2];
pair<int,int> def[2] = {{INF, INF}, {-INF, -INF}};
void build(int id, int l, int r, int j) {
if (l == r) {
seg[id][j] = {a[l], l};
return;
}
int mid = (l+r)/2;
build(id*2, l, mid, j); build(id*2+1, mid+1, r, j);
if (j == 0) seg[id][j] = min(seg[id*2][j], seg[id*2+1][j]);
if (j == 1) seg[id][j] = max(seg[id*2][j], seg[id*2+1][j]);
}
pair<int,int> qry(int id, int l, int r, int findl, int findr, int j) {
if (findr < l || r < findl) return def[j];
if (findl <= l && r <= findr) return seg[id][j];
int mid = (l+r)/2;
if (j == 0) return min(qry(id*2, l, mid, findl, findr, j), qry(id*2+1, mid+1, r, findl, findr, j));
else return max(qry(id*2, l, mid, findl, findr, j), qry(id*2+1, mid+1, r, findl, findr, j));
}
pair<int,int> mx(int l, int r) {
return qry(1, 1, n, l, r, 1);
}
int mn(int l, int r) {
return qry(1, 1, n, l, r, 0).first;
}
void init(int32_t N, std::vector<int32_t> H) {
n = N;
for (int i=0;i<n;i++) a[i+1] = H[i];
sum[0] = 0;
for (int i=1;i<=n;i++) sum[i] = (i > 1 && i < n && a[i] > a[i-1] && a[i] > a[i+1]) + sum[i-1];
build(1, 1, n, 0);
build(1, 1, n, 1);
}
int d;
vector<pair<int,int>> vec;
void solve(int l, int r) {
if (l > r) return;
auto [val, mid] = mx(l, r);
solve(l, mid-1); solve(mid+1, r);
// cout << l << " " << r << " " << lim << " " << lhs + rhs << " " << (int)(mn(l, r) <= lim) << endl;
int lhs = mn(l, mid-1), rhs = mn(mid+1, r);
if (lhs <= val - d && rhs <= val - d) {
int L = l, R = mid-1;
while (L < R) {
int M = (L+R+1)/2;
if (mn(M, mid-1) <= val - d) L = M;
else R = M - 1;
}
int ll = L;
L = mid+1, R = r;
while (L < R) {
int M = (L+R)/2;
if (mn(mid+1, M) <= val - d) R = M;
else L = M + 1;
}
int rr = R;
vec.push_back({ll, rr});
}
}
struct node {
int val, lhs, rhs;
};
node seg2[8000005];
int cnt = 0;
void build2(int id, int l, int r) {
seg2[id] = {(int)0, id*2, id*2+1};
cnt = max(id, cnt);
if (l == r) return;
int mid = (l+r)/2;
build2(id*2, l, mid); build2(id*2+1, mid+1, r);
}
int update2(int id, int l, int r, int target) {
if (r < target || target < l) return id;
cnt++;
seg2[cnt] = seg2[id];
id = cnt;
seg2[id].val++;
if (l == r) return id;
int mid = (l+r)/2;
seg2[id].lhs = update2(seg2[id].lhs, l, mid, target);
seg2[id].rhs = update2(seg2[id].rhs, mid+1, r, target);
return id;
}
int qry2(int id, int l, int r, int findl, int findr) {
if (r < findl || findr < l) return 0;
if (findl <= l && r <= findr) return seg2[id].val;
int mid = (l+r)/2;
return qry2(seg2[id].lhs, l, mid, findl, findr) + qry2(seg2[id].rhs, mid+1, r, findl, findr);
}
bool cmp(pair<int,int> x, pair<int,int> y) {
return x.first > y.first;
}
bool inited = false;
int sz;
int t[maxn];
void init2() {
inited = true;
solve(1, n);
sort(vec.begin(), vec.end(), cmp);
sz = vec.size();
build2(1, 1, n);
for (int i=1;i<=n;i++) t[i] = 0;
int last = 1;
for (int i=0;i<sz;i++) {
t[vec[i].first] = max(update2(last, 1, n, vec[i].second), t[vec[i].first]);
last = t[vec[i].first];
// cout << vec[i].first << " " << vec[i].second << endl;
}
for (int i=n-1;i>=1;i--) t[i] = max(t[i], t[i+1]);
// for (int i=1;i<=n;i++) cout << t[i] << " "; cout << endl;
// for (int i=1;i<=n;i++) cout << qry2(t[1], 1, n, i, i) << " "; cout << endl;
}
int32_t max_towers(int32_t L, int32_t R, int32_t D) {
if (!inited) {d = D; init2();}
L++, R++;
return 1 + qry2(t[L], 1, n, 1, R);
}
