#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],sp[17][100069],lg2[100069];
multiset<long long> ms;
multiset<pair<long long,pair<long long,long long>>> rg;
bitset<100069> spc;
struct segtree
{
long long l,r,sm;
pair<long long,long long> mxl,mxr;
segtree *p[2];
void bd(long long lb,long long rb)
{
l=lb;
r=rb;
if(l==r)
{
sm=spc[l];
mxl={spc[l],-l};
mxr={spc[l],l};
}
else
{
long long ii,md=(l+r)/2;
for(ii=0;ii<2;ii++)
{
p[ii]=new segtree;
p[ii]->bd(!ii?l:md+1,!ii?md:r);
}
sm=p[0]->sm+p[1]->sm;
mxl=max(p[0]->mxl,p[1]->mxl);
mxr=max(p[0]->mxr,p[1]->mxr);
}
}
void ud(long long x,long long w)
{
if(l>=x&&r<=x)
{
sm+=w;
mxl.fr+=w;
mxr.fr+=w;
}
else
{
long long ii;
for(ii=0;ii<2;ii++)
{
if(!(p[ii]->l>x||p[ii]->r<x))
{
segtree *tmp=p[ii];
p[ii]=new segtree;
*p[ii]=*tmp;
p[ii]->ud(x,w);
}
}
sm=p[0]->sm+p[1]->sm;
mxl=max(p[0]->mxl,p[1]->mxl);
mxr=max(p[0]->mxr,p[1]->mxr);
}
}
long long qrs(long long lb,long long rb)
{
if(l>rb||r<lb)
{
return 0;
}
else if(l>=lb&&r<=rb)
{
return sm;
}
else
{
return p[0]->qrs(lb,rb)+p[1]->qrs(lb,rb);
}
}
pair<long long,long long> qrxl(long long lb,long long rb)
{
if(l>rb||r<lb)
{
return {-inf,-1};
}
else if(l>=lb&&r<=rb)
{
return mxl;
}
else
{
return max(p[0]->qrxl(lb,rb),p[1]->qrxl(lb,rb));
}
}
pair<long long,long long> qrxr(long long lb,long long rb)
{
if(l>rb||r<lb)
{
return {-inf,-1};
}
else if(l>=lb&&r<=rb)
{
return mxr;
}
else
{
return max(p[0]->qrxr(lb,rb),p[1]->qrxr(lb,rb));
}
}
}
sg[100069];
inline void spbd()
{
long long i,j,k;
for(i=1;i<=n;i++)
{
sp[0][i]=a[i];
}
for(i=1;1ll<<i<=n;i++)
{
for(j=1;j<=n-(1ll<<i)+1;j++)
{
sp[i][j]=min(sp[i-1][j],sp[i-1][j+(1ll<<i-1)]);
}
}
for(i=1;i<=n;i++)
{
for(k=i;k>1;k/=2,lg2[i]++);
}
}
inline long long spqr(long long lb,long long rb)
{
long long e=lg2[rb-lb+1];
return min(sp[e][lb],sp[e][rb-(1ll<<e)+1]);
}
void init(int on,vector<int> aa)
{
long long i,k,l=-1,w,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;
spc[i]=1;
}
}
sg[0].bd(1,n);
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;
}
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}});
}
udn++;
uds[udn]=w;
sg[udn]=sg[udn-1];
sg[udn].ud(k,-1);
sg[udn].ud(l,-1);
}
spbd();
}
int max_towers(int lb,int rb,int cw)
{
long long k,w,w2,w3,p,mn,z;
pair<long long,long long> tmp;
lb++;
rb++;
p=lower_bound(uds+1,uds+udn+1,cw)-uds-1;
w=sg[p].sm;
w2=sg[p].qrs(1,lb-1);
w3=sg[p].qrs(rb+1,n);
z=(max(w-(w2+1)/2*2-(w3+1)/2*2,0ll)+1)/2;
if(w2%2)
{
tmp=sg[p].qrxl(lb,rb);
if(tmp.fr)
{
k=-tmp.sc;
mn=spqr(lb,k-1);
z+=a[k]-mn>=cw;
}
}
if(w3%2)
{
tmp=sg[p].qrxr(lb,rb);
if(tmp.fr)
{
k=tmp.sc;
mn=spqr(k+1,rb);
z+=a[k]-mn>=cw;
}
}
z=max(z,1ll);
return z;
}
