#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
struct pi{
int h,x,y;
};
bool operator<(const pi &a, const pi &b){
return a.h>b.h;
}
priority_queue<pi> pq;
set<int> st;
map<int,int> re;
void init(int N, std::vector<int> H) {
bool ch = false;
if(N==1) st.insert(0);
for(int i=1;i<N;i++){
if(!ch&&H[i-1]<H[i]){
st.insert(i-1);
ch = true;
}
else if(ch&&H[i-1]>H[i]){
st.insert(i-1);
ch = false;
}
}
if(!ch) st.insert(N-1);
//for(auto x:st) printf("%d\n",x);
auto it = st.begin(), nit = it;
nit++;
while(nit!=st.end()){
pq.push({abs(H[*nit]-H[*it]),*it,*nit});
it++; nit++;
}
int d=0;
while(!pq.empty()){
int h=pq.top().h,x=pq.top().x,y=pq.top().y; pq.pop();
if(!st.count(x)||!st.count(y)) continue;
//printf("%d %d %d %d\n",h,x,y,(int)st.size());
if(h!=d){
re[d+1]=((int)st.size()-1)/2+1;
//printf("%d %d\n",d,re[d+1]);
d=h;
}
st.erase(x); st.erase(y);
it=st.lower_bound(x); nit=st.upper_bound(y);
if(it!=st.begin()&&nit!=st.end()){
it--;
pq.push({abs(H[*nit]-H[*it]),*it,*nit});
}
}
re[d+1]=1;
}
int max_towers(int L, int R, int D) {
auto it = re.upper_bound(D);
it--;
return it->second;
}
