#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fall(i,a,b) for(int i=a;i<=b;i++)
#define rfall(i,a,b) for(int i=a;i>=b;i--)
#define sz(x) (int) x.size()
#define pb push_back
#define all(x) (int)x.size()
const int MAXN=1e5+10;
const ll inf=1e17;
typedef pair<int,int> pii;
struct node{
int best,v1,v2;
bool full;
node operator+(const node& nd){
node c;
c.best=max({this->best,nd.best}); c.full=((this->full)&nd.full);
c.v1=this->v1;
if(this->full) c.v1+=nd.v1;
c.v2=nd.v2;
if(nd.full) c.v2+=this->v2;
c.best=max(c.best,this->v2+nd.v1);
return c;
}
};
int n;
node seg[4*MAXN];
vector<ll> v;
void build(int ind,int l,int r){
if(l==r){
seg[ind].v1=seg[ind].v2=seg[ind].best=seg[ind].full=(v[l]==1);
return;
}
int m=(l+r)>>1; build(2*ind,l,m); build(2*ind+1,m+1,r);
seg[ind]=seg[2*ind]+seg[2*ind+1];
}
node query(int ind,int l,int r,int a,int b){
if(a>r || l>b) return{0,0,0,1};
if(a<=l && b>=r) return seg[ind];
int m=(l+r)>>1;
return query(2*ind,l,m,a,b)+query(2*ind+1,m+1,r,a,b);
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,std::vector<int> R) {
n=sz(H);
for(auto u:H) v.pb(u);
vector<ll> ans(sz(L));
build(1,0,n-1);
fall(i,0,sz(L)-1){
auto c=query(1,0,n-1,L[i],R[i]);
ans[i]=2*(R[i]-L[i]+1)-c.best;
}
return ans;
}
