#include "meetings.h"
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;
long long v[100005];
long long aib[100015];
int nmax=100005;
long long rasp[100005];
vector<pair<int,int> > qu[100005];
void update(int poz,long long val)
{
while(poz<=nmax)
{
aib[poz]=max(aib[poz],val);
poz=poz+(poz&(-poz));
}
}
long long query(int poz)
{
long long sum=0;
while(poz)
{
sum=max(sum,aib[poz]);
poz=poz-(poz&(-poz));
}
return sum;
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R) {
int Q = L.size();
int n=H.size();
for(int i=1;i<=n;i++)
{
v[i]=H[i-1];
}
for(int i=0;i<Q;i++)
{
qu[L[i]+1].push_back({R[i]+1,i});
}
int lung=0;
for(int st=n;st>=1;st--)
{
if(v[st]==1)
{
lung++;
}
else
{
int poz=st;
for(int j=1;j<=lung;j++)
{
update(st+j,j);
}
lung=0;
}
for(auto j:qu[st])
{
if(j.first<=st+lung-1)
{
rasp[j.second]=j.first-st+1;
}
else
{
rasp[j.second]=2*(j.first-st+1)-max((long long)lung,query(j.first));
}
}
}
vector<long long>rez;
for(int i=0;i<Q;i++)
{
rez.push_back(rasp[i]);
}
return rez;
}
