#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct nodo{
ll suma;
ll respuesta;
ll prefijo;
ll sufijo;
};
template<class T>
struct SegmentTree{
T (*merge)(T, T);
ll n;
vector<T>ST;
void build(ll i, ll l, ll r, vector<T> &values){
if (l == r){
ST[i] = values[l];
return;
}
build(i * 2, l, (l + r) / 2, values);
build(i * 2 + 1, (l + r) / 2 + 1, r, values);
ST[i] = merge(ST[i * 2], ST[i * 2 + 1]);
}
SegmentTree(vector<T> &values, T (*merge)(T a, T b)) : merge(merge){
n = values.size();
ST.resize(n << 2 | 3);
build(1, 0, n - 1, values);
}
void update(ll i, ll l, ll r, ll pos, T val){
if (r < pos or l > pos) return;
if (l == r){
ST[i] = val;
return;
}
update(i << 1, l, (l + r) >> 1, pos, val);
update(i << 1 | 1, (l + r) / 2 + 1, r, pos, val);
ST[i] = merge(ST[i << 1], ST[i << 1 | 1]);
}
void update(ll pos, T val){
update(1, 0, n - 1, pos, val);
}
T query(ll i, ll l, ll r, ll a, ll b){
if (l >= a and r <= b) return ST[i];
ll mid = (l + r) >> 1;
if (mid < a)
return query(i << 1 | 1, mid + 1, r, a, b);
if (mid >= b)
return query(i << 1, l, mid, a, b);
return merge(query(i << 1, l, mid, a, b), query(i << 1 | 1, mid + 1, r, a, b));
}
T query(ll a, ll b){
if (a > b) return merge(query(1, 0, n - 1, 0, b), query(1, 0, n - 1, a, n - 1));
return query(1, 0, n - 1, a, b);
}
};
nodo merge(nodo a,nodo b){
nodo c;
c.suma=a.suma+b.suma;
c.prefijo=max(a.prefijo,a.suma+b.prefijo);
c.sufijo=max(b.sufijo,b.suma+a.sufijo);
c.respuesta=max({a.sufijo+b.prefijo,a.respuesta,b.respuesta});
return c;
}
vector<ll> minimum_costs(vector<int> H, vector<int> L,vector<int> R) {
ll n=H.size();
ll Q = L.size();
if(n>5000||Q>5000){
vector<long long> C(Q);
vector<vector<ll>>dp(n,vector<ll>(n));
for(ll i=0;i<n;i++){
ll max_height=(ll)H[i];
dp[i][i]=max_height;
for(ll l=i-1;l>=0;l--){
max_height=max(max_height,(ll)H[l]);
dp[i][l]=(dp[i][l+1]+max_height);
}
max_height=H[i];
for(ll r=i+1;r<n;r++){
max_height=max(max_height,(ll)H[r]);
dp[i][r]=(dp[i][r-1]+max_height);
}
}
for(ll q=0;q<Q;q++){
C[q]=LLONG_MAX;
for(ll i=L[q];i<=R[q];i++){
C[q]=min(C[q],dp[i][L[q]]+dp[i][R[q]]-H[i]);
}
}
return C;
}
else{
vector<ll> C(Q);
vector<nodo>nuevo;
for(ll i=0;i<n;i++){
nodo anadir;
if(H[i]==2){
anadir.suma=-INT_MAX;
anadir.respuesta=-INT_MAX;
anadir.prefijo=-INT_MAX;
anadir.sufijo=-INT_MAX;
nuevo.push_back(anadir);
}
else{
anadir.suma=1;
anadir.respuesta=1;
anadir.prefijo=1;
anadir.sufijo=1;
nuevo.push_back(anadir);
}
}
SegmentTree<nodo>st(nuevo,merge);
for(ll q=0;q<Q;q++){
ll l=L[q];
ll r=R[q];
ll maxsequenceofones=st.query(l,r).respuesta;
if(maxsequenceofones<=0){
C[q]=2*(r-l+1);
}
else{
ll falta=(r-l+1)-(maxsequenceofones);
C[q]=(maxsequenceofones+(2*falta));
}
}
return C;
}
}
