#include<bits/stdc++.h>
using namespace std;
#define intt long long
#define pb push_back
#define forr(i , x , y) for(int i = x; i <= y;i++)
#define fore(i , n) for(int i = 0 ; i < n;i++)
#define forn(i ,x , y) for(int i = x ; i >= y;i--)
namespace {
int read_int() {
int x;
if (scanf("%d", &x) != 1) {
fprintf(stderr, "Error while reading input\n");
exit(1);
}
return x;
}
} // namespace
const intt INF = 1e18;
struct segTree
{
int BASE;
vector<int> tree;
segTree(int n , vector<int> &temp)
{
BASE = n;
while(__builtin_popcount(BASE) != 1)
BASE++;
tree.assign(2*BASE , 0);
fore(i , n)
tree[i + BASE] = temp[i];
forn(i , BASE - 1 , 0)
tree[i] = max(tree[2*i] , tree[2*i + 1]);
}
int query(int l , int r)
{
l+=BASE;
r+=BASE;
if(l == r)
return tree[l];
int lt = tree[l] , rt = tree[r];
while (l +1 < r)
{
if(l%2 == 0)
{
lt = max(lt , tree[l + 1]);
}
if(r%2 == 1)
rt = max(tree[r - 1] , rt);
l>>=1;
r>>=1;
}
return max(lt , rt);
}
};
vector<long long> minimum_costs(vector<int> H, vector<int> L , vector<int> R)
{
int n = (int)H.size();
fore(i , n)
H[i]--;
int q = (int)L.size();
vector<int> nxt(n + 2) , prv(n + 1) , temp(n);
prv[0] = 0;
nxt[n + 1] = n + 1;
forr(i , 1 , n)
{
if(H[i - 1] == 1)
prv[i] = i;
else
prv[i] = prv[i - 1];
}
forn(i , n , 1)
{
if(H[i - 1] == 1)
nxt[i] = i;
else
nxt[i] = nxt[i + 1];
}
forr(i , 0 , n - 1)
{
temp[i] = nxt[i + 1] - prv[i + 1];
}
segTree seg(n , temp);
vector<intt> ans(q , INF);
fore(i , q)
{
int l = L[i] , r = R[i];
if(nxt[l + 1] > r + 1)
ans[i] = r - l + 1;
else
{
int val = 0;
int _l = nxt[l + 1] - 1, _r = prv[r + 1] - 1;
if(H[r] == 0)
ans[i] = min(ans[i] , (2LL)*(_r - l + 1));
if(H[l] == 0)
ans[i] = min(ans[i] , (2LL) * (r - _l + 1));
val = max(val , seg.query(_l , _r));
ans[i] = min({ans[i] , 2LL * (r - l + 1) , 2LL * (r - l + 2 - val)});
}
}
return ans;
}
