#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
#define maxn 100050
vector<int> sum(maxn*4,0);
vector<int> prefix(maxn*4,0);
vector<int> suffix(maxn*4,0);
vector<int> maximum(maxn*4,0);
vector<int> vect1;
void build(int node,int start,int end){
if(start==end){
if(vect1[start]==1){
prefix[node] = suffix[node] = sum[node] = 1;
}
else{
sum[node] = 1;
}
return;
}
int mid = (start+end)/2;
build(node*2+1,start,mid);
build(node*2+2,mid+1,end);
if(prefix[node*2+1]==sum[node*2+1]){
prefix[node] = prefix[node*2+1]+prefix[node*2+2];
}
else{
prefix[node] = prefix[node*2+1];
}
if(suffix[node*2+2]==sum[node*2+2]){
suffix[node] = suffix[node*2+2]+suffix[node*2+1];
}
else{
suffix[node] = suffix[node*2+2];
}
sum[node] = sum[node*2+2]+sum[node*2+1];
maximum[node] = max(prefix[node*2+2]+suffix[node*2+1],max(maximum[node*2+1],maximum[node*2+2]));
}
int an = 0;
vector<int> query(int node,int start,int end,int rangemin,int rangemax){
//cout << start << " " << end << endl;
if(start>rangemax||end<rangemin){
return {0,0,0};
}
if(start>=rangemin&&end<=rangemax){
an = max(an,maximum[node]);
return {prefix[node],suffix[node],sum[node]};
}
int mid = (start+end)/2;
vector<int> a = query(node*2+1,start,mid,rangemin,rangemax);
vector<int> b = query(node*2+2,mid+1,end,rangemin,rangemax);
if(a[0]==-1){
return b;
}
if(b[0]==-1){
return a;
}
an = max(an,a[1]+b[0]);
vector<int> ret(3);
ret[2] = a[2]+b[2];
if(a[0]==a[2]){
ret[0] = a[0]+b[0];
}
else{
ret[0] = a[0];
}
if(b[1]==b[2]){
ret[1] = b[1]+a[1];
}
else{
ret[1] = b[1];
}
//cout << start << " " << end << " " << ret[0] << " " << ret[1] << " " << ret[2] << "\n";
return ret;
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R) {
vector<long long int> ans(L.size());
vect1 = H;
build(0,0,vect1.size()-1);
for(int i=0;i<L.size();i++){
query(0,0,vect1.size()-1,L[i],R[i]);
//cout << an << "\n";
ans[i] = (R[i]-L[i]+1)*2-an;
an = 0;
}
return ans;
}
