#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
const int nmax=5e3+42;
long long pref[nmax][nmax],suff[nmax][nmax];//left -> start, right-> to
const int SZ=4e5+42;
struct info
{
int pref,suff,best,sz;
};
info tree[SZ];
info my_merge(info le,info ri)
{
info ret;
ret.sz=le.sz+ri.sz;
ret.pref=le.pref;
if(le.pref==le.sz)ret.pref+=ri.pref;
ret.suff=ri.suff;
if(ri.suff==ri.suff)ret.suff+=le.suff;
ret.sz=le.sz+ri.sz;
ret.best=max(le.best,ri.best);
ret.best=max(ret.best,le.suff+ri.pref);
return ret;
}
void update(int node,int l,int r,int pos,int val)
{
if(l==r)
{
tree[node].sz=1;
tree[node].pref=(val==0?1:0);
tree[node].suff=tree[node].pref;
tree[node].best=tree[node].pref;
return;
}
int av=(l+r)/2;
if(pos<=av)update(node*2,l,av,pos,val);
else update(node*2+1,av+1,r,pos,val);
tree[node]=my_merge(tree[node*2],tree[node*2+1]);
}
info query(int node,int l,int r,int lq,int rq)
{
if(l==lq&&r==rq)return tree[node];
int av=(l+r)/2;
if(rq<=av)return query(node*2,l,av,lq,rq);
if(av<lq)return query(node*2+1,av+1,r,lq,rq);
return my_merge(query(node*2,l,av,lq,av),query(node*2+1,av+1,r,av+1,rq));
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R)
{
int n=H.size();
if(H.size()<=5000)
{
for(int le=0;le<n;le++)
{
int maxi=H[le];
suff[le][le]=maxi;
for(int ri=le+1;ri<n;ri++)
{
maxi=max(maxi,H[ri]);
suff[le][ri]=suff[le][ri-1]+maxi;
}
}
for(int le=0;le<n;le++)
{
int maxi=H[le];
pref[le][le]=maxi;
for(int ri=le-1;ri>=0;ri--)
{
maxi=max(maxi,H[ri]);
pref[le][ri]=pref[le][ri+1]+maxi;
}
}
/*
for(int le=0;le<n;le++)
for(int ri=0;ri<n;ri++)
cout<<le<<" "<<ri<<" -> "<<pref[le][ri]<<" "<<suff[le][ri]<<endl;
*/
vector<long long> outp={};
for(int i=0;i<L.size();i++)
{
outp.push_back(1e18);
for(int j=L[i];j<=R[i];j++)
{
//cout<<L[i]<<" "<<R[i]<<" "<<j<<" -> "<<pref[j][L[i]]<<" "<<suff[j][R[i]]<<" "<<H[j]<<endl;
outp[i]=min(outp[i],pref[j][L[i]]+suff[j][R[i]]-H[j]);
}
}
return outp;
}
else
{
for(int i=0;i<n;i++)
update(1,0,n-1,i,H[i]-1);
vector<long long> outp={};
for(int i=0;i<L.size();i++)
{
outp.push_back(2*(R[i]-L[i]+1));
outp[i]=outp[i]-query(1,0,n-1,L[i],R[i]).best;
}
return outp;
}
}
