#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(a) (a).begin(), (a).end()
#define ll long long
template<typename T>
int len(T &a){
return a.size();
}
int n;
vector<int> h;
int mx = 0;
struct SegTree{
int n;
vector<int> t;
SegTree(int n) : n(n), t(2 * n){}
SegTree(){}
int merge(int a, int b){
return max(a, b);
}
void upd(int i, int x){
i += n;
t[i] = max(t[i], x);
for(i /= 2; i > 0; i /= 2){
t[i] = merge(t[i * 2], t[i * 2 + 1]);
}
}
int get(int l, int r){
l += n; r += n;
int res = 0;
while(l <= r){
if(l & 1){
res = merge(res, t[l ++]);
}
if(!(r & 1)) res = merge(res, t[r --]);
l /= 2;
r /= 2;
}
return res;
}
};
void init(int N, std::vector<int> H) {
n = N;
h = H;
for(int i = 0; i < n; i ++){
if(h[mx] < h[i]){
mx = i;
}
}
}
int max_towers(int l, int r, int d) {
vector<int> hh;
for(int i = l; i <= r; i ++) hh.push_back(h[i]), hh.push_back(h[i] - d),hh.push_back(h[i] + d);
sort(all(hh));
hh.erase(unique(all(hh)), hh.end());
auto getid = [&](int x)->int{
return lower_bound(all(hh), x) - hh.begin();
};
SegTree st1(len(hh) + 1), st2(len(hh) + 1);
for(int i = l; i <= r; i ++){
int j = getid(h[i]);
st1.upd(j, st2.get(getid(h[i] + d), len(hh)) + 1);
st2.upd(j, st1.get(0, getid(h[i] - d)));
//cout << st2.get(j, j) << ' ';
}
return st1.get(0, len(hh));
}
