#include "meetings.h"
#include <numeric>
using namespace std;
#define ALL(x) begin(x),end(x)
#define pb push_back
#define F first
#define S second
// #define int long long
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
typedef vector<vb> vvb;
template<typename T>
T meq(T& a, T b){
return a=max(a,b);
}
#define D 20
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();
std::vector<long long> C(Q);
vi left(n),right(n);
iota(ALL(left),0);
iota(ALL(right),0);
for (int i=0;i<n-1;i++)if(H[i]==1&&H[i+1]==1)left[i+1]=left[i];
for (int i=n-1;i>0;i--)if(H[i]==1&&H[i-1]==1)right[i-1]=right[i];
vi lg(n+1);
lg[0]=-10000000;lg[1]=0;
for (int i=2;i<=n;i++)lg[i]=lg[i/2]+1;
vvi mxs(D, vi(n)); // height, ind
for (int i=0;i<n;i++)mxs[0][i]=(H[i]==1)?right[i]-left[i]+1:0;
for (int d=1;d<D;d++){
for (int i=0;i<n;i++){
mxs[d][i]=mxs[d-1][i];
if(i+(1<<(d-1))<n)meq(mxs[d][i],mxs[d-1][i+(1<<(d-1))]);
}
}
auto solve = [&](int l, int r) -> ll {
int len = r-l+1;
int l2 = l, r2 = r, ans = 2*len;
if (H[l]==1){
l2 = right[l]+1;
ans=min(ans,2*len+l-right[l]-1);
}
if (H[r]==1){
r2 = left[r];
ans=min(ans,2*len-r+left[r]-1);
}
int len2 = r2-l2;
if (len2){
int d = lg[len2];
ans = min(ans, 2*len-max(mxs[d][l2], mxs[d][r2-(1<<d)]));
}
return ans;
};
for (int j = 0; j < Q; ++j) {
C[j] = solve(L[j], R[j]);
}
return C;
}
