#include "meetings.h"
using namespace std;
typedef long long ll;
struct Data
{
int pre,suf,mx,len;
};
const int LG=20,N=1e5+10;
Data sp[N][LG];
Data merge(Data a,Data b)
{
Data ans;
ans.mx=max(a.mx,b.mx);
ans.pre=a.pre+b.pre*(a.pre==a.len);
ans.suf=a.suf*(b.suf==b.len)+b.suf;
ans.mx=max(ans.mx,a.suf+b.pre);
ans.len=a.len+b.len;
return ans;
}
int get(int ql,int qr)
{
qr++;
Data cur={0,0,0,0};
for(int j=LG-1;j>=0;j--)
{
if((ql+(1<<j))<=qr)
{
cur=merge(cur,sp[ql][j]);
ql+=(1<<j);
}
}
return cur.mx;
}
std::vector<long long> minimum_costs(std::vector<int> h, std::vector<int> l,
std::vector<int> r) {
int n=h.size(),q=l.size(),mx=2;
for(int i=0;i<n;i++)
{
mx=max(mx,h[i]);
}
if(mx==2)
{
for(int i=0;i<n;i++)
{
if(h[i]==2)
{
sp[i][0]={0,0,0,1};
}
else if (h[i]==1)
{
sp[i][0]={1,1,1,1};
}
}
for(int j=1;j<LG;j++)
{
for(int i=0;i+(1<<j)<=n;i++)
sp[i][j]=merge(sp[i][j-1],sp[i+(1<<(j-1))][j-1]);
}
vector<ll> fpp;
for(int i=0;i<q;i++)
{
fpp.push_back(2*(r[i]-l[i]+1)-get(l[i],r[i]));
}
return fpp;
// we want the maximum segment of ones in range l,r
}
vector<ll> fnl(q);
vector<ll> cst(n+2,0);
for(int i=0;i<q;i++)
{
int ql=l[i],qr=r[i];
vector<int> c;
ll ans=0;
for(int x=ql;x<=qr;x++)
{
while(c.size()>0 and h[c.back()]<=h[x])
{
int z=c.back();
c.pop_back();
ans-=1ll*(z-((c.size()>0)?(c.back()):(ql-1)))*h[z];
}
int z=x;
ans+=1ll*(z-((c.size()>0)?(c.back()):(ql-1)))*h[z];
c.push_back(x);
cst[x]=ans;
}
ans=0;
ll mi=1e18;
c.clear();
for(int x=qr;x>=ql;x--)
{
while(c.size()>0 and h[c.back()]<=h[x])
{
int z=c.back();
c.pop_back();
ans-=1ll*(((c.size()>0)?(c.back()):(qr+1))-z)*h[z];
}
int z=x;
ans+=1ll*(((c.size()>0)?(c.back()):(qr+1))-z)*h[z];
c.push_back(x);
mi=min(mi,cst[x]+ans-h[x]);
}
fnl[i]=mi;
}
return fnl;
}
