#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e18L + 20;
struct node {
int len, max_all, max_pref, max_suf;
node(): len(0), max_all(0), max_pref(0), max_suf(0) {};
node(int _len, int _max_all, int _max_pref, int _max_suf): len(_len), max_all(_max_all), max_pref(_max_pref), max_suf(_max_suf) {};
};
long long sum_l[5020][5020];
long long sum_r[5020][5020];
node tree[400020];
int H[100020];
node merge(node left, node right) {
node res;
res.len = left.len + right.len;
res.max_pref = left.max_pref + (left.max_pref == left.len ? right.max_pref : 0);
res.max_suf = right.max_suf + (right.max_suf == right.len ? left.max_suf : 0);
res.max_all = max({left.max_all, right.max_all, left.max_suf + right.max_pref, res.max_pref, res.max_suf});
return res;
}
void build(int id, int lt, int rt) {
if (lt == rt) {
tree[id] = node(1, (H[lt] == 1), (H[lt] == 1), (H[lt] == 1));
return;
}
int mt = (lt + rt) / 2;
build(id * 2, lt, mt);
build(id * 2 + 1, mt + 1, rt);
tree[id] = merge(tree[id * 2], tree[id * 2 + 1]);
}
node get(int id, int lt, int rt, int ql, int qr) {
if (lt == ql && rt == qr) {
return tree[id];
}
int mt = (lt + rt) / 2;
if (qr <= mt) {
return get(id * 2, lt, mt, ql, qr);
}
else if (ql >= mt + 1) {
return get(id * 2 + 1, mt + 1, rt, ql, qr);
}
else {
return merge(get(id * 2, lt, mt, ql, mt), get(id * 2 + 1, mt + 1, rt, mt + 1, qr));
}
}
vector<long long> minimum_costs(vector<int> _H, vector<int> L, vector<int> R) {
int N = _H.size();
for (int i = 0; i < N; i++) {
H[i] = _H[i];
}
int Q = L.size();
if (N <= 5000) {
for (int i = 0; i < N; i++) {
int mx = 0;
long long sum = 0;
for (int j = i; j >= 0; j--) {
mx = max(mx, H[j]);
sum += mx;
sum_l[j][i] = sum;
}
mx = 0;
sum = 0;
for (int j = i; j < N; j++) {
mx = max(mx, H[j]);
sum += mx;
sum_r[i][j] = sum;
}
}
vector<long long> res(Q, inf);
for (int i = 0; i < Q; i++) {
for (int j = L[i]; j <= R[i]; j++) {
res[i] = min(res[i], sum_l[L[i]][j] + sum_r[j][R[i]] - H[j]);
}
}
return res;
}
else {
build(1, 0, N - 1);
vector<long long> res(Q);
for (int i = 0; i < Q; i++) {
res[i] = (R[i] - L[i] + 1) * 2 - get(1, 0, N - 1, L[i], R[i]).max_all;
}
return res;
}
return vector<long long>();
}
