#include"towers.h"
#include<vector>
#include<iostream>
using namespace std;
int n;
vector<int>arr;
vector<int>thres;
vector<int>prv,nxt;
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_thres(){
thres.resize(n);
for(int i=0;i<n;i++){
int mn=2e9;
if(prv[i]!=-1){
int mx1=0;
for(int j=i;j>prv[i];j--)
mx1=max(mx1,arr[j]);
mn=min(mn,mx1);
}
if(nxt[i]!=-1){
int mx2=0;
for(int j=i;j<nxt[i];j++)
mx2=max(mx2,arr[j]);
mn=min(mn,mx2);
}
thres[i]=mn-arr[i];
}
}
void init(int N,vector<int>H){
arr=H;
n=(int)arr.size();
init_prev();
init_nxt();
init_thres();
}
int max_towers(int L,int R,int D){
int first=-1,last=-1;
int res=0;
for(int i=L;i<=R;i++){
if(thres[i]>=D){
res++;
if(first==-1)
first=i;
last=i;
}
}
if(first==-1){
int sm=L;
for(int i=L;i<=R;i++)
if(arr[i]<arr[sm])
sm=i;
int mx=0;
for(int i=sm;i<=R;i++){
if(arr[i]<=mx-D)
return 2;
mx=max(mx,arr[i]);
}
mx=0;
for(int i=sm;i>=L;i--){
if(arr[i]<=mx-D)
return 2;
mx=max(mx,arr[i]);
}
return 1;
}
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;
}
