#include "towers.h"
#include<bits/stdc++.h>
#include <vector>
#define fr first
#define sc second
using namespace std;
const int N = 100010;
int v[N];
int lf[N], rf[N], dp[N], max_dp[N], folha[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;
return a;
}
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 sou_folha[N];
int n;
int st = 1;
int nodes[N];
int ll[N], rr[N];
void build(int& node, int l, int r, int D){
if(l > r) return;
if(l == r){
nodes[l] = node;
lf[node] = rf[node] = 0;
dp[node] = 1;
max_dp[node] = 0;
folha[node] = v[l];
ll[node] = l;
rr[node] = r;
node++;
sou_folha[l] = 1;
return;
}
int pos = seg.query(1, l, r, 1, n).second;
int nd = node;
ll[nd] = l;
rr[nd] = r;
node++;
nodes[pos] = nd;
if(l <= pos-1){
lf[nd] = node;
build(node, l, pos-1, D);
}
else{
lf[nd] = 0;
}
if(pos+1 <= r){
rf[nd] = node;
build(node, pos+1, r, D);
}
else{
rf[nd] = 0;
}
max_dp[nd] = max(max_dp[lf[nd]], max_dp[rf[nd]]);
folha[nd] = min(folha[lf[nd]], folha[rf[nd]]);
int esq = (lf[nd] != 0 ? max(max_dp[lf[nd]], (folha[lf[nd]] <= v[pos]-D ? 1 : 0)) : 0);
int dir = (rf[nd] != 0 ? max(max_dp[rf[nd]], (folha[rf[nd]] <= v[pos]-D ? 1 : 0)) : 0);
dp[nd] = esq+dir;
max_dp[nd] = max(max_dp[nd], dp[nd]);
return;
}
int pref[N];
void init(int NN, std::vector<int> h) {
n = NN;
for(int i = 1;i <= n;i++)
v[i] = h[i-1];
lf[0] = rf[0] = -1;
dp[0] = -1e9;
max_dp[0] = -1e9;
folha[0] = 1e9+1;
seg.build(1, 1, n);
build(st, 1, n, 1);
for(int i = 1;i <= n;i++){
//cout << nodes[i] << ' ';
pref[i] = pref[i-1]+sou_folha[i];
}
//cout << '\n';
}
int add(int x, int L, int R){
// x nao pode ser folha e ele nao pode ter folhas embaixo dele
if(sou_folha[x]) return 0;
if(lf[nodes[x]] != 0){
int v = lf[nodes[x]];
if(rr[v] >= L) return 0;
}
if(rf[nodes[x]] != 0){
int v = rf[nodes[x]];
if(ll[v] <= R) return 0;
}
return 1;
}
int max_towers(int L, int R, int D) {
L++;
R++;
//cout << pref[R] << ' ' << pref[L-1] << ' ' << sou_folha[L] << ' ' << nodes[L] << ' ' << rf[nodes[L]] << '\n';
return pref[R]-pref[L-1]+add(L, L, R)+add(R, L, R) - (L==R ? 1 : 0);
}
