#include "towers.h"
#include <bits/stdc++.h>
#define f first
#define s second
#define ent '\n'
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 12;
int root[maxn], t[maxn * 30];
int L[maxn * 30], R[maxn * 30];
int p[20][maxn], lg[maxn];
int dp[maxn], a[maxn];
pair<int, int> ord[maxn];
map<int, int> position;
int n, nv;
int build(int l, int r){
int v = ++nv;
if(l == r) return v;
int mid = l + r >> 1;
L[v] = build(l, mid);
R[v] = build(mid+1, r);
return v;
}
int upd(int v, int tl, int tr, int pos, int x){
int u = ++nv;
if(tl == tr){
t[u] = x;
return u;
}
L[u] = L[v], R[u] = R[v];
int mid = tl + tr >> 1;
if(pos <= mid){
L[u] = upd(L[v], tl, mid, pos, x);
}
else{
R[u] = upd(R[v], mid+1, tr, pos, x);
}
t[u] = t[L[u]] + t[R[u]];
return u;
}
int get(int v, int tl, int tr, int l, int r){
if(tl > r || l > tr) return 0;
if(tl >= l && tr <= r) return t[v];
int mid = tl + tr >> 1;
return get(L[v], tl, mid, l, r) + get(R[v], mid+1, tr, l, r);
}
int get(int v, int tl, int tr, int k){
if(tl == tr) return tl;
int mid = tl + tr >> 1;
if(t[L[v]] >= k) return get(L[v], tl, mid, k);
return get(R[v], mid+1, tr, k - t[L[v]]);
}
struct asd{
int mx, mn, x, y;
} d[maxn * 4];
asd merge(asd x, asd y){
if(x.mx < 0) return y;
if(y.mx < 0) return x;
x.x = max({x.x, y.x, y.mx - x.mn});
x.y = max({x.y, y.y, x.mx - y.mn});
x.mx = max(x.mx, y.mx);
x.mn = min(x.mn, y.mn);
return x;
}
void build(int v, int tl, int tr){
if(tl == tr){
d[v].mx = d[v].mn = a[tl];
d[v].x = d[v].y = 0;
}
else{
int mid = tl + tr >> 1;
build(v*2, tl, mid);
build(v*2+1, mid+1, tr);
d[v] = merge(d[v*2], d[v*2+1]);
}
}
asd query(int v, int tl, int tr, int l, int r){
if(tl > r || l > tr) return {-1, -1, -1, -1};
if(tl >= l && tr <= r) return d[v];
int mid = tl + tr >> 1;
return merge(query(v*2, tl, mid, l, r), query(v*2+1, mid+1, tr, l, r));
}
int get(int l, int r){
if(l > r) return 0;
int k = lg[r - l + 1];
return max(p[k][l], p[k][r - (1 << k) + 1]);
}
void init(int N, std::vector<int> H) {
n = N;
for(int i=1;i<=n;i++){
dp[i] = int(2e9) + 1;
a[i] = p[0][i] = H[i - 1];
position[a[i]] = i;
if(i > 1) lg[i] = lg[i / 2] + 1;
}
for(int k=1;k<20;k++){
for(int i=1;i + (1 << k) - 1 <= n;i++){
p[k][i] = max(p[k-1][i], p[k-1][i + (1 << (k - 1))]);
}
}
stack<int> s;
for(int i=1;i<=n;i++){
while(s.size() && a[s.top()] > a[i]){
s.pop();
}
if(s.size()){
dp[i] = get(s.top() + 1, i - 1);
}
s.push(i);
}
while(s.size()) s.pop();
for(int i=n;i;i--){
while(s.size() && a[s.top()] > a[i]){
s.pop();
}
if(s.size()){
dp[i] = min(dp[i], get(i + 1, s.top() - 1));
}
s.push(i);
ord[i] = {dp[i] - a[i], i};
}
sort(ord + 1, ord + n + 1, [](pair<int, int> x, pair<int, int> y){
return x > y;
});
root[0] = build(1, n);
build(1, 1, n);
for(int i=1;i<=n;i++){
root[i] = upd(root[i-1], 1, n, ord[i].s, 1);
}
}
int max_towers(int l, int r, int d) {
l++, r++;
int i = l, j = r, pos = 0;
for(int tl = 1, tr = n; tl <= tr;){
int mid = tl + tr >> 1;
if(ord[mid].f >= d){
pos = mid;
tl = mid + 1;
}
else tr = mid - 1;
}
int sx = get(root[pos], 1, n, 1, l - 1) + 1, sy = get(root[pos], 1, n, l, r), ans = sy;
if(sy == 0){
i = j = position[query(1, 1, n, l, r).mn];
ans = 1;
}
else{
i = get(root[pos], 1, n, sx), j = get(root[pos], 1, n, sx + sy - 1);
}
int L = 0, R = 0;
for(int tl = l + 1, tr = i - 1; tl <= tr;){
int mid = tl + tr >> 1;
if(query(1, 1, n, mid, i-1).mx >= a[i] + d){
L = mid;
tl = mid + 1;
}
else tr = mid - 1;
}
for(int tl = j + 1, tr = r - 1; tl <= tr;){
int mid = tl + tr >> 1;
if(query(1, 1, n, j + 1, mid).mx >= a[j] + d){
R = mid;
tr = mid - 1;
}
else tl = mid + 1;
}
if(L != 0 && query(1, 1, n, l, L).x >= d) ans++;
if(R != 0 && query(1, 1, n, R, r).y >= d) ans++;
return ans;
}
