#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 4e5+5, INF = 1e9;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair
#define pb push_back
#define fr first
#define sc second
vector<int> h;
struct no{
int l, r, ms, sum;
};
no operator + (no a, no b) {
no c;
c.l = max(a.l, a.sum + b.l);
c.r = max(b.r, b.sum + a.r);
c.ms = max({a.ms, b.ms, a.r + b.l});
c.sum = a.sum + b.sum;
return c;
}
no seg[4*MAXN];
void build(int node, int l, int r) {
if(l == r) {
seg[node].sum = h[l];
seg[node].l = seg[node].r = seg[node].ms = max(0,h[l]);
return;
}
int mid = (l+r)/2;
build(2*node, l, mid);
build(2*+node+1, mid+1, r);
seg[node] = seg[2*node] + seg[2*node+1];
}
no query(int node, int l, int r, int p, int q) {
if(r < p or q < l) return {-INF, -INF, -INF, -INF};
if(p <= l and r <= q) return seg[node];
int mid = (l+r)/2;
return query(2*node, l, mid, p, q) + query(2*node+1, mid+1, r, p, q);
}
vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
int N = sz(H), Q = sz(L), maxval = 0;
for(int i = 0; i < N; maxval = max(maxval, H[i]), i++)
if(H[i] == 1) h.pb(1);
else h.pb(-N);
if(maxval > 2) {
vector<ll> ans(Q,1e15), p(N);
vector<int> v(N);
for(int i = 0; i < N; i++) {
v[i] = H[i];
for(int j = i-1; j >= 0; j--)
v[j] = max(v[j+1], H[j]);
for(int j = i+1; j < N; j++)
v[j] = max(v[j-1], H[j]);
p[0] = v[0];
for(int j = 1; j < N; j++) p[j] = p[j-1] + v[j];
for(int j = 0; j < Q; j++)
ans[j] = min(ans[j], p[R[j]] - p[L[j]] + v[L[j]]);
}
return ans;
}
else {
build(1, 0, N-1);
vector<ll> ans(Q);
for(int i = 0; i < Q; i++) {
int k = query(1, 0, N-1, L[i], R[i]).ms;
ans[i] = k + (R[i] - L[i] + 1)*2;
}
return ans;
}
}
