#include <bits/stdc++.h>
#define vi vector<int>
#define gi greater<int>
#define gr greater
#define ve vector
#define ll long long
#define vf vector<float>
#define vll vector<pair<ll,ll>>
#define ii pair<int,int>
#define pll pair<ll,ll>
#define vvi vector<vi>
#define vii vector<ii>
#define gii greater<ii>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF 1e18
#define eps 1e-7
#define eps1 1e-2
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX_A 2e5+5
using namespace std;
const int MOD = 1e9+7;
const int nax = 5005+5;
typedef complex<int> Point;
//#define X real()
//#define Y imag()
//#include "meetings.h"
ll st[nax*4], s[nax];
void build(int v, int l, int r){
if(l == r){
st[v] = s[l];
return;
}
int md =(l+r)/2;
build(v*2,l,md);
build(v*2+1,md+1,r);
st[v] = max(st[v*2], st[v*2+1]);
}
int query(int v, int l, int r, int i, int j){
if(r < i || l > j) return 0;
if(i <= l && r <= j) return st[v];
int md = (l+r)/2;
return max(query(v*2,l,md,i,j), query(v*2+1, md+1, r, i, j));
}
ve<ll> minimum_costs(vi h, vi l, vi r) {
int n = h.size();
vi ind;
int cnt = 0;
for (int i = 0; i < n; ++i)
{
if(h[i] == 1){
cnt++;
} else {
if(cnt){
ind.pb(i);
s[i] = cnt;
}
cnt = 0;
}
}
build(1,0,n);
if(cnt) {
ind.pb(n);
}
int q = l.size();
ve<ll> ans(q);
for (int i = 0; i < q; ++i)
{
//cout << "YES" << i << endl;
int st = *upper_bound(ind.begin(), ind.end(), l[i]),
nd = *upper_bound(ind.begin(), ind.end(), r[i]);
int mx = 0;
if(st != nd){
mx = max(min(st-l[i], query(1,0,n, st, st)), max(0, query(1,0,n, nd, nd) - (nd-r[i]-1)));
st++,nd--;
if(st <= nd){
mx = max(mx, query(1,0,n,st,nd));
}
} else {
mx = min(max(0, query(1,0,n, nd, nd) - (nd-r[i]-1)), r[i]-l[i]+1);
}
ans[i] = mx + ((r[i]-l[i]+1) - mx)*2;
}
return ans;
}
