#include <bits/stdc++.h>
#include "towers.h"
using namespace std;
#define mp make_pair
#define fr first
#define sc second
const long long inf=1e18;
long long n,udn=0,a[100069],uds[100069],sq[100069];
multiset<long long> ms;
multiset<pair<long long,pair<long long,long long>>> rg;
void init(int on,vector<int> aa)
{
long long i,k,l=-1,w,c=0,k2,l2;
n=on;
for(i=1;i<=n;i++)
{
a[i]=aa[i-1];
}
ms.insert(-inf);
ms.insert(inf);
for(i=1;i<=n;i++)
{
if(((i==1||a[i]<a[i-1])&&(i==n||a[i]<a[i+1]))||(i>1&&i<n&&a[i]>max(a[i-1],a[i+1])))
{
ms.insert(i);
if(l!=-1)
{
rg.insert({abs(a[l]-a[i]),{l,i}});
}
l=i;
c++;
}
}
c=(c+1)/2;
sq[0]=c;
for(;!rg.empty();)
{
w=rg.begin()->fr;
k=rg.begin()->sc.fr;
l=rg.begin()->sc.sc;
rg.erase(rg.begin());
if(ms.find(k)==ms.end()||ms.find(l)==ms.end())
{
continue;
}
c--;
udn++;
uds[udn]=w;
sq[udn]=c;
ms.erase(k);
ms.erase(l);
k2=*prev(ms.lower_bound(k));
l2=*ms.upper_bound(l);
if(k2!=-inf&&l2!=inf)
{
rg.insert({abs(a[k2]-a[l2]),{k2,l2}});
}
}
}
int max_towers(int lb,int rb,int cw)
{
long long p=lower_bound(uds+1,uds+udn+1,cw)-uds-1;
return sq[p];
}
