#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 nn=0,a[100069],ex[100069],zs=0;
multiset<long long> ms;
priority_queue<pair<long long,pair<long long,long long>>> pq;
bitset<100069> vtd;
pair<long long,long long> sq[100069];
void init(int n,vector<int> aa)
{
long long i,k,l,w,e=0;
multiset<long long>::iterator it;
for(i=1;i<=n;i++)
{
a[i]=aa[i-1];
}
a[0]=inf;
a[n+1]=inf;
for(i=1;i<=n;i++)
{
if(a[i]<a[i-1]&&a[i]<a[i+1])
{
if(!e)
{
nn++;
ex[nn]=i;
e=1;
}
}
else if(a[i]>a[i-1]&&a[i]>a[i+1])
{
if(e)
{
nn++;
ex[nn]=i;
e=0;
}
}
}
if(!e)
{
nn--;
}
for(i=1;i<=nn;i++)
{
ms.insert(ex[i]);
}
for(i=1;i<=nn-1;i++)
{
pq.push({-abs(a[ex[i]]-a[ex[i+1]]),{ex[i],ex[i+1]}});
}
zs++;
sq[zs]={0,(nn+1)/2};
for(;!pq.empty();)
{
w=-pq.top().fr;
k=pq.top().sc.fr;
l=pq.top().sc.sc;
pq.pop();
if(vtd[k]||vtd[l])
{
continue;
}
zs++;
sq[zs]={w,sq[zs-1].sc-1};
ms.erase(k);
ms.erase(l);
vtd[k]=1;
vtd[l]=1;
it=ms.lower_bound(k);
if(it==ms.begin())
{
continue;
}
k=*prev(it);
it=ms.upper_bound(l);
if(it==ms.end())
{
continue;
}
l=*it;
pq.push({-abs(a[k]-a[l]),{k,l}});
}
}
int max_towers(int lb,int rb,int cw)
{
lb++;
rb++;
if(lb==rb)
{
return 1;
}
else
{
long long p;
p=lower_bound(sq+1,sq+zs+1,mp((long long)cw,-inf))-sq-1;
return sq[p].sc;
}
}
