#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100000;
vector<int> val, all;
int numval;
struct segtree {
int seg[4 * maxn];
void update(int curin, int curl, int curr, int in, int val) {
if (in < curl || in > curr) return;
if (curl == curr) {
seg[curin] = max(seg[curin], val);
return;
}
update(curin * 2 + 1, curl, (curl + curr) / 2, in, val),
update(curin * 2 + 2, (curl + curr) / 2 + 1, curr, in, val);
seg[curin] = max(seg[curin * 2 + 1], seg[curin * 2 + 2]);
}
int query(int curin, int curl, int curr, int ql, int qr) {
if (ql > curr || qr < curl) return 0;
if (ql <= curl && curr <= qr) return seg[curin];
return max(query(curin * 2 + 1, curl, (curl + curr) / 2, ql, qr),
query(curin * 2 + 2, (curl + curr) / 2 + 1, curr, ql, qr));
}
} up, down;
void init(int N, vector<int> H) {
all = H;
set<int> si;
for (int i = 0; i < N; i++) si.insert(H[i]);
numval = si.size();
for (auto a : si) val.push_back(a);
// for (auto a : val) cout << a << ' ';
// cout << "\n";
}
int max_towers(int L, int R, int D) {
memset(up.seg, 0, sizeof up.seg);
memset(down.seg, 0, sizeof down.seg);
for (int i = L; i <= R; i++) {
int small =
upper_bound(val.begin(), val.end(), all[i] - D) - val.begin() - 1;
int exact = lower_bound(val.begin(), val.end(), all[i]) - val.begin();
int higher = lower_bound(val.begin(), val.end(), all[i] + D) - val.begin();
// cout << i << ' ' << L << ' ' << R << " ";
// cout << small << " " << exact << " " << higher << "\n";
if (small >= 0)
down.update(0, 0, numval - 1, exact,
up.query(0, 0, numval - 1, 0, small));
if (higher >= 0)
up.update(0, 0, numval - 1, exact,
down.query(0, 0, numval - 1, higher, numval - 1) + 1);
// cout << "UP: ";
// for (int i = 0; i < numval; i++)
// cout << up.query(0, 0, numval - 1, i, i) << " ";
// cout << "\nDOWN: ";
// for (int i = 0; i < numval; i++)
// cout << down.query(0, 0, numval - 1, i, i) << " ";
// cout << "\n";
}
return up.query(0, 0, numval - 1, 0, numval - 1);
}
