#include "meetings.h"
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
const int N = 1e5 + 10;
struct node {
int mx, suf, pref, l, r;
} t[4 * N];
node neutral = {-1, -1, -1, -1, -1};
node merge(node a, node b) {
if(a.mx == -1) return b;
if(b.mx == -1) return a;
node c;
c.l = a.l, c.r = b.r;
c.mx = max({a.mx, b.mx, a.suf + b.pref});
c.pref = a.pref;
c.suf = b.suf;
if(a.pref == a.r - a.l + 1) {
c.pref = max(c.pref, a.pref + b.pref);
}
if(b.suf == b.r - b.l + 1) {
c.suf = max(c.suf, b.suf + a.suf);
}
return c;
}
void build(int i, int l, int r, vector<int>& h) {
if(l > r) return;
if(l == r) {
t[i].pref = t[i].mx = t[i].suf = (h[l] == 1);
t[i].l = t[i].r = l;
return;
}
int mid = l + r >> 1;
build(2 * i, l, mid, h);
build(2 * i + 1, mid + 1, r, h);
t[i] = merge(t[2 * i], t[2 * i + 1]);
}
node query(int i, int l, int r, int tl, int tr) {
if(l > tr || r < tl) return neutral;
if(l >= tl && r <= tr) return t[i];
int mid = l + r >> 1;
return merge(query(2 * i, l, mid, tl, tr), query(2 * i + 1, mid + 1, r, tl, tr));
}
vector<long long> minimum_costs(vector<int> h, vector<int> l, vector<int> r) {
for(int i = 0; i < 4 * N; ++i) t[i] = neutral;
int q = l.size(), n = h.size();
vector<ll> ans(q);
build(1, 0, n - 1, h);
if(n > 5000) {
for(int i = 0; i < q; ++i) {
node x = query(1, 0, n - 1, l[i], r[i]);
ans[i] = x.mx + (r[i] - l[i] + 1 - x.mx) * 2;
}
} else {
vector<vector<ll>> right(n, vector<ll>(n, 0)), left(n, vector<ll>(n, 0));
for(int i = 0; i < n; ++i) {
int mx = h[i];
for(int r = i; r < n; ++r) {
mx = max(mx, h[r]);
right[i][r] += mx + (r > i ? right[i][r - 1] : 0);
}
mx = h[i];
for(int l = i - 1; l >= 0; --l) {
mx = max(mx, h[l]);
left[i][l] += mx + left[i][l + 1];
}
}
for(int i = 0; i < q; ++i) {
ans[i] = LLONG_MAX;
for(int j = l[i]; j <= r[i]; ++j) {
ll valnow = right[j][r[i]] + left[j][l[i]];
ans[i] = min(ans[i], valnow);
}
}
}
return ans;
}
