#include "towers.h"
#include<bits/stdc++.h>
using namespace std;
//#define int int64_t
int M = 1000000002;
vector<int> u;
int n;
void init(int N, std::vector<int> H) {
n = N;
vector<int> w(N , M);
stack<array<int , 2>> a;
a.push({0 , M});
for(int i = 0; i < N; i++){
int o = 0;
while(a.top()[0]>H[i]){
o = max(o , a.top()[1]);
a.pop();
}
a.top()[1] = max(a.top()[1] , o);
w[i] = min(w[i] , a.top()[1]-H[i]+1);
a.push({H[i] , H[i]});
}
while(!a.empty())a.pop();
a.push({0 , M});
for(int i = N-1; i >= 0; i--){
int o = 0;
while(a.top()[0]>H[i]){
o = max(o , a.top()[1]);
a.pop();
}
a.top()[1] = max(a.top()[1] , o);
w[i] = min(w[i] , a.top()[1]-H[i]+1);
a.push({H[i] , H[i]});
}
for(int i = 0; i < N; i++){
u.push_back(w[i]);
}
sort(u.begin() , u.end());
}
int max_towers(int L, int R, int D) {
return n-(upper_bound(u.begin() , u.end() , D)-u.begin());
}
