#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<double> cd;
const int MAXN = 1e5+10;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
struct Node{
int sum, pref, suff, ans;
Node(int a=0, int b=0, int c=0, int d=0): sum(a), pref(b), suff(c), ans(d) {}
Node operator+ (Node a) const{
Node res;
res.sum=this->sum+a.sum;
res.pref=max(this->pref, this->sum+a.pref);
res.suff=max(this->suff+a.sum, a.suff);
res.ans=max({this->ans, a.ans, this->suff+a.pref});
return res;
}
};
Node tree[4*MAXN];
void upd(int node, int l, int r, int p, int val){
if(r<p || l>p) return;
if(l==r){
tree[node]=Node(val, val, val, val);
return;
}
int mid=(l+r)>>1;
upd(node*2, l, mid, p, val); upd(node*2+1, mid+1, r, p, val);
tree[node]=tree[node*2]+tree[node*2+1];
}
Node query(int node, int l, int r, int p, int q){
if(r<p || l>q) return Node(-1e8, -1e8, -1e8, -1e8);
if(l>=p && r<=q) return tree[node];
int mid=(l+r)>>1;
return query(node*2, l, mid, p, q)+query(node*2+1, mid+1, r, p, q);
}
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
int q=(int)L.size(), n=(int)H.size();
if(n<=5000){
vector<ll> ans(q);
vector<vector<ll>> res(n, vector<ll>(n));
for(int i=0;i<n;i++){
res[i][i]=H[i];
int curr=H[i];
for(int j=i+1;j<n;j++){
curr=max(curr, H[j]);
res[i][j]=res[i][j-1]+curr;
}
curr=H[i];
for(int j=i-1;j>=0;j--){
curr=max(curr, H[j]);
res[i][j]=res[i][j+1]+curr;
}
}
for(int i=0;i<q;i++){
ll best=LINF;
for(int j=L[i];j<=R[i];j++) best=min(best, res[j][L[i]]+res[j][R[i]]-H[j]);
ans[i]=best;
}
return ans;
}
for(int i=0;i<n;i++){
if(H[i]==1) upd(1, 0, n-1, i, 1);
else upd(1, 0, n-1, i, -1e8);
}
vector<ll> ans(q);
for(int i=0;i<q;i++){
Node interv=query(1, 0, n-1, L[i], R[i]);
//~ cout << interv.ans << "\n";
int res=2*(R[i]-L[i]+1);
if(interv.ans>=0) res-=interv.ans;
ans[i]=res;
}
return ans;
}
