#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
using vi = vector<int>;
using vvi = vector<vi>;
struct SegTree {
int N, neutral;
vi st, arr;
function<int(int, int)> combine;
SegTree(int _N, vi _arr, function<int(int, int)> _combine, int _neutral) {
N = _N; arr = _arr; combine = _combine, neutral = _neutral;
st.assign(4 * N, 0);
build(0, 0, N);
}
SegTree() : N(0), neutral(0) {};
int build(int i, int l, int r) {
if (l + 1 == r) return st[i] = arr[l];
int m = l + (r - l) / 2;
return st[i] = combine(build(2 * i + 1, l, m), build(2 * i + 2, m, r));
}
int query(int i, int l, int r, int ql, int qr) {
if (r <= ql || qr <= l) return neutral;
if (ql <= l && r <= qr) return st[i];
int m = l + (r - l) / 2;
return combine(query(2 * i + 1, l, m, ql, qr), query(2 * i + 2, m, r, ql, qr));
}
int update(int i, int l, int r, int k, int v) {
if (!(l <= k && k < r)) return st[i];
if (l + 1 == r) return st[i] = arr[k] = v;
int m = l + (r - l) / 2;
return combine(update(2 * i + 1, l, m, k, v), update(2 * i + 2, m, r, k, v));
}
int query(int l, int r) {
return query(0, 0, N, l, r);
}
void update(int k, int v) {
update(0, 0, N, k, v);
}
};
struct DSU {
int N;
vi par, siz, mv;
set<int> components;
DSU(int _N, vi _mv) {
N = _N;
par.resize(N); iota(par.begin(), par.end(), 0);
siz.assign(N, 1);
mv = _mv;
components = set<int>(all(par));
}
DSU() : N(0) {};
int find_set(int v) {
if (v == par[v]) return v;
return par[v] = find_set(par[v]);
}
void union_set(int nA, int nB) {
int a = find_set(nA);
int b = find_set(nB);
if (a != b) {
cout << "Union of " << nA << " and " << nB << "\n";
if (siz[a] > siz[b]) {
siz[a] += siz[b];
par[b] = a;
mv[a] = min(mv[b], mv[a]);
components.erase(b);
} else {
siz[b] += siz[a];
par[a] = b;
mv[b] = min(mv[b], mv[a]);
components.erase(a);
}
}
}
};
int n;
vi h;
SegTree minST;
/*
If tower i is connected to tower j, and tower j is connected to tower k (i < m1 < j < m2 < k)
- tower i and k are connected through either m1 or m2
*/
void init(int N, vi H) {
n = N; h = H;
minST = SegTree(n, h, [](int a, int b) {return max(a, b);}, INT_MIN);
}
int max_towers(int L, int R, int D) {
// cout << "\n\n----------------------\n";
int ans = 1; // 1 is always possible
auto dsu = DSU(n, h);
for (int i = L; i <= R; i++) {
int tl = 0;
int left = i;
int chmax = INT_MIN;
for (int right = left + 1; right <= R; right++) {
if (h[left] + D <= chmax && h[right] + D <= chmax) {
tl++;
chmax = INT_MIN;
}
chmax = max(chmax, h[right]);
}
ans = max(ans, tl);
}
// ans = *max_element(all(dsu.siz));
// cout << "----------------------\n\n";
return ans;
}
