#include<bits/stdc++.h>
#include "towers.h"
#include <vector>
#define fr first
#define sc second
using namespace std;
const int N = 2010;
int v[N];
struct Segtree{
pair <int, int> tree[4*N];
pair <int, int> join(pair <int, int> a, pair <int, int> b){
if(a.fr > b.fr) return a;
if(a.fr < b.fr) return b;
if(a.sc > b.sc) return a;
return b;
}
void build(int node, int l, int r){
if(l == r){
tree[node] = {v[l], l};
return;
}
int mid = (l+r)/2;
build(2*node, l, mid);
build(2*node+1, mid+1, r);
tree[node] = join(tree[2*node], tree[2*node+1]);
return;
}
pair <int, int> query(int node, int l, int r, int tl, int tr){
if(l > tr or tl > r) return {-1, 0};
if(l <= tl and tr <= r) return tree[node];
int mid = (tl+tr)/2;
return join(query(2*node, l, r, tl, mid), query(2*node+1, l,r, mid+1, tr));
}
} seg;
int n;
void init(int mm, std::vector<int> h) {
n = mm;
for(int i = 1;i <= n;i++)
v[i] = h[i-1];
seg.build(1, 1, n);
}
int dp[N][N];
int max_towers(int L, int R, int D) {
L++;
R++;
for(int i = L-1;i <= R;i++){
dp[L-1][i] = 0;
}
for(int i = L;i <= R;i++){
for(int j = i+1;j <= R+1;j++){
if(j == R+1){
dp[i][j] = max(dp[i-1][j], dp[i-1][i]+1);
continue;
}
dp[i][j] = max(dp[i-1][j], (seg.query(1, i+1, j-1, 1, n).first-D >= max(v[i], v[j]) ? dp[i-1][i]+1 : 0));
}
}
return dp[R][R+1];
}
