#include"towers.h"
#include<vector>
#include<iostream>
using namespace std;
int n;
vector<int>arr;
vector<int>thres;
vector<int>prv,nxt;
vector<vector<int>>arr_rmq;
vector<vector<int>>thres_rmq;
void init_prev(){
prv.resize(n);
vector<int>s;
for(int i=0;i<n;i++){
while(s.size()&&arr[s.back()]>arr[i])
s.pop_back();
if(s.empty())
prv[i]=-1;
else
prv[i]=s.back();
s.push_back(i);
}
}
void init_nxt(){
nxt.resize(n);
vector<int>s;
for(int i=n-1;i>=0;i--){
while(s.size()&&arr[s.back()]>arr[i])
s.pop_back();
if(s.empty())
nxt[i]=-1;
else
nxt[i]=s.back();
s.push_back(i);
}
}
void init_arr_rmq(){
arr_rmq=vector<vector<int>>(20,vector<int>(n));
arr_rmq[0]=arr;
for(int p=1;p<20;p++){
for(int i=0;i+(1<<p)<=n;i++){
arr_rmq[p][i]=max(arr_rmq[p-1][i],arr_rmq[p-1][i+(1<<(p-1))]);
}
}
}
int get_arr_max(int l,int r){
int pw2=2;
int p=0;
while(pw2<r-l){
pw2*=2;
p++;
}
pw2/=2;
return max(arr_rmq[p][l],arr_rmq[p][r-pw2]);
}
void init_thres(){
thres.resize(n);
for(int i=0;i<n;i++){
int mn=2e9;
if(prv[i]!=-1){
int mx1=get_arr_max(prv[i],i);
mn=min(mn,mx1);
}
if(nxt[i]!=-1){
int mx2=get_arr_max(i,nxt[i]);
mn=min(mn,mx2);
}
thres[i]=mn-arr[i];
}
}
void init_thres_rmq(){
thres_rmq=vector<vector<int>>(20,vector<int>(n));
thres_rmq[0]=thres;
for(int p=1;p<20;p++){
for(int i=0;i+(1<<p)<=n;i++){
thres_rmq[p][i]=max(thres_rmq[p-1][i],thres_rmq[p-1][i+(1<<(p-1))]);
}
}
}
int get_thres_max(int l,int r){
int pw2=2;
int p=0;
while(pw2<r-l){
pw2*=2;
p++;
}
pw2/=2;
return max(thres_rmq[p][l],thres_rmq[p][r-pw2]);
}
void init(int N,vector<int>H){
arr=H;
n=(int)arr.size();
init_prev();
init_nxt();
init_arr_rmq();
init_thres();
init_thres_rmq();
}
int max_towers(int L,int R,int D){
int res=0;
for(int i=L;i<=R;i++){
if(thres[i]>=D){
res++;
}
}
int first=-1,last=-1;
if(get_thres_max(L,R+1)<D){
first=L;
for(int i=L;i<=R;i++)
if(arr[i]<arr[first])
first=i;
res=1;
last=first;
}else{
{
int l=L,r=R+1;
while(l<r-1){
int mid=(l+r)/2;
if(get_thres_max(L,mid)>=D)
r=mid;
else
l=mid;
}
first=l;
}
{
int l=L,r=R+1;
while(l<r-1){
int mid=(l+r)/2;
if(get_thres_max(mid,R+1)>=D)
l=mid;
else
r=mid;
}
last=l;
}
}
int mx=0;
for(int i=first;i>=L;i--){
if(max(arr[i],arr[first])+D<=mx){
res++;
break;
}
mx=max(mx,arr[i]);
}
mx=0;
for(int i=last;i<=R;i++){
if(max(arr[i],arr[last])+D<=mx){
res++;
break;
}
mx=max(mx,arr[i]);
}
return res;
}
