#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
#define vf first
#define vs second
#define mp(x,y) make_pair(x,y)
struct Seg {
int siz = 1;
vector<int> sums;
void init(int n){
while(siz < n)siz*=2;
sums.assign(siz * 2, 0LL);
}
void set(int i , int v , int x , int lx , int rx){
if(rx - lx ==1){
sums[x] = v;
return;
}
int m = (lx + rx) / 2;
if(i < m){
set(i , v , 2 * x + 1 , lx , m);
}
else {
set(i , v , 2 * x + 2 , m , rx);
}
sums[x]=max(sums[2 * x + 1] , sums[2 * x + 2]);
}
void set(int x , int y){
set(x ,y , 0 , 0 , siz);
}
int sum(int l , int r , int x , int lx , int rx){
if(lx >= l && rx <= r){
return sums[x];
}
if(lx >= r || rx <= l)return 0;
int m = (lx + rx) / 2;
return max(sum(l , r , 2 * x + 1 , lx , m) , sum(l , r , 2 * x + 2 , m , rx));
}
int sum(int l , int r){
return sum(l , r , 0 , 0 , siz);
}
};
vector<int> arr;
void init(int n, std::vector<int> h) {
arr = h;
}
int max_towers(int l , int r , int d) {
Seg st;
int n = arr.size();
st.init(n+1);
set<pair<int,int>> s;
int dp[n];
int left[n];
for(int i = n - 1; i >= 0; i--){
while(s.size() && (*(s.begin())).vf <= arr[i] - d){
left[(*(s.begin())).vs] = i;
s.erase(s.begin());
}
s.insert(mp(arr[i] , i));
}
while(s.size()){
left[(*(s.begin())).vs] = -1;
s.erase(s.begin());
}
set<pair<int,pair<int,int>>> s1;
//for(int i = 0; i < n; i++)cout << left[i] << ' ';
memset(dp,0,sizeof dp);
for(int i = l; i <= r; i++){
dp[i] = 1;
while(s1.size() && (*(s1.begin())).vf <= arr[i] - d){
int pos = (*(s1.begin())).vs.vs;
dp[pos] = max(dp[pos] , (*(s1.begin())).vs.vf);
st.set(pos , dp[pos]);
s1.erase(s1.begin());
}
if(i > 0)dp[i] = max(dp[i] , dp[i-1]);
int cur = 1;
int p = left[i];
if(p >= l){
cur += st.sum(l , p);
}
s1.insert(mp(arr[i] , mp(cur , i)));
}
while(s1.size()){
int pos = (*(s1.begin())).vs.vs;
dp[pos] = max(dp[pos] , (*(s1.begin())).vs.vf);
s1.erase(s1.begin());
}
int ans = 0;
for(int i = l; i <= r; i++)ans = max(ans , dp[i]);
return ans;
}
