#include <bits/stdc++.h>
using namespace std;
#define ll long long
class SegTree {
private:
int n;
vector<int> seg;
void update(int node, int l, int r, int idx, int v) {
if (l == r) {
seg[node] = v;
}
else {
int mid = (l + r) / 2;
if (idx <= mid) update(node*2+1, l, mid, idx, v);
else update(node*2+2, mid+1, r, idx, v);
}
}
int query(int node, int start, int end, int l, int r) {
if (start > r || end < l) return 0;
else if (start >=l && end <= r) return seg[node];
else {
int mid = (start + end) / 2;
return max(query(node*2+1, start, mid, l, r), query(node*2+2, mid+1, end, l, r));
}
}
public:
SegTree(int nn) {
n = nn;
seg.assign((nn+2)*4, 0);
}
void update(int idx, int v) {
update(0, 0, n-1, idx, v);
}
int query(int l, int r) {
return query(0, 0, n-1, l, r);
}
};
vector<ll> minimum_costs(vector<int> h, vector<int> L, vector<int> R) {
int n = h.size();
int q = L.size();
vector<ll> ans;
vector<int> er(n, 0), el(n, 0);
for (int i = 1; i < n; i++) {
if (h[i] == 2) el[i] = i;
else el[i] = el[i-1];
}
for (int i = n-2; i >= 0; i--) {
if (h[i] == 2) er[i] = i;
else er[i] = er[i+1];
}
SegTree seg(n);
for (int i = 0; i < n; i++) {
if (h[i] == 2) continue;
seg.update(i, er[i] - i);
}
for (int curr = 0; curr < q; curr++) {
int l = L[curr];
int r = R[curr];
int maxSeg = 0;
if (l == r) {
ans.push_back((ll)h[l]);
continue;
}
if (h[l] == 1) {
if (er[l] > r) {
ans.push_back(r - l + 1);
continue;
}
maxSeg = max(maxSeg, er[l] - l);
l = er[l];
}
if (h[r] == 1) {
maxSeg = max(maxSeg, r - el[r]);
r = el[r];
}
maxSeg = max(maxSeg, seg.query(l, r));
ans.push_back(maxSeg + 2 * ((r - l + 1) - maxSeg));
}
return ans;
/*
for (int curr = 0; curr < q; curr++) {
int l = L[curr];
int r = R[curr];
vector<ll> dpl(n, 0), dpr(n, 0);
stack<pair<int, int>> st;
for (int i = l; i <= r; i++) {
int cov = 1;
while (!st.empty() && h[st.top().first] <= h[i]) {
cov += st.top().second;
st.pop();
}
dpl[i] = (ll)cov * (ll)h[i];
if (!st.empty()) dpl[i] += dpl[st.top().first];
st.push({i, cov});
}
while (!st.empty()) st.pop();
for (int i = r; i >= l; i--) {
int cov = 1;
while (!st.empty() && h[st.top().first] <= h[i]) {
cov += st.top().second;
st.pop();
}
dpr[i] = (ll)cov * (ll)h[i];
if (!st.empty()) dpr[i] += dpr[st.top().first];
st.push({i, cov});
}
ll fin = dpl[l] + dpr[l];
for (int i = l; i <= r; i++) fin = min(fin, dpl[i] + dpr[i] - (ll)h[i]);
ans.push_back(fin);
}
return ans;
*/
}
