#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
const int N=100010, S=(1<<18);
int n, ans=1, a[N], d[N];
vector<int> c;
vector<int> v[N];
class seg {
public:
void update(int k, int v) {
k+=S-1;
tree[k]=max(tree[k], v);
for(k>>=1; k; k>>=1) tree[k]=max(tree[k], v);
}
int query(int l, int r) {
int ret=0;
for(l+=S-1, r+=S-1; l<r; l>>=1, r>>=1) {
if(l&1) ret=max(ret, tree[l++]);
if(!(r&1)) ret=max(ret, tree[r--]);
}
if(l==r) ret=max(ret, tree[l]);
return ret;
}
private:
int tree[2*S];
}T1, T2;
void init(int N, vector<int> H) {
n=N;
for(int i=1; i<=n; i++) a[i]=H[i-1];
}
int max_towers(int L, int R, int D) {
L++, R++;
fill(d+L, d+R+1, 1);
for(int i=L; i<=R; i++) T1.update(i, a[i]);
for(int i=L; i<=R; i++) {
int tmp=R+1;
for(int s=i+1, e=R; s<=e; ) {
int m=(s+e)/2;
if(T1.query(i+1, m)>=a[i]+D) tmp=m, e=m-1;
else s=m+1;
}
v[tmp+1].push_back(i);
}
for(int i=L; i<=R; i++) c.push_back(a[i]), c.push_back(a[i]-D);
sort(c.begin(), c.end()), c.erase(unique(c.begin(), c.end()), c.end());
for(int i=L; i<=R; i++) {
for(int j:v[i]) T2.update(lower_bound(c.begin(), c.end(), a[j]-D)-c.begin()+1, d[j]+1);
d[i]=max(d[i], T2.query(lower_bound(c.begin(), c.end(), d[i])-c.begin()+1, S));
ans=max(ans, d[i]);
}
return ans;
}
