#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll inf = 1e18;
vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
int N = H.size(), Q = L.size();
if (N <= 5000 && Q <= 5000) {
vector<ll> ans(Q, inf);
for (int i = 0; i < Q; i++) {
vector<int> stk;
vector<ll> A(N);
for (int j = L[i]; j <= R[i]; j++) {
while (!stk.empty() && H[stk.back()] <= H[j]) {
stk.pop_back();
}
if (stk.empty()) {
A[j] = 1LL * H[j] * (j - (L[i] - 1));
} else {
A[j] = 1LL * H[j] * (j - stk.back()) + A[stk.back()];
}
stk.push_back(j);
}
stk.clear();
vector<ll> B(N);
for (int j = R[i]; j >= L[i]; j--) {
while (!stk.empty() && H[stk.back()] <= H[j]) {
stk.pop_back();
}
if (stk.empty()) {
B[j] = 1LL * H[j] * ((R[i] + 1) - j);
} else {
B[j] = 1LL * H[j] * (stk.back() - j) + B[stk.back()];
}
stk.push_back(j);
}
for (int j = L[i]; j <= R[i]; j++) {
ans[i] = min(ans[i], A[j] + B[j] - H[j]);
}
}
return ans;
}
vector LC(N, vector<int>(21, -1));
for (int i = 0; i < N; i++) {
if (i) {
LC[i] = LC[i - 1];
}
LC[i][H[i]] = i;
}
vector RC(N, vector<int>(21, N));
for (int i = N - 1; i >= 0; i--) {
if (i < N - 1) {
RC[i] = RC[i + 1];
}
RC[i][H[i]] = i;
}
vector<int> LS(N), LP(N), stk;
for (int i = 0; i < N; i++) {
while (!stk.empty() && H[stk.back()] <= H[i]) {
stk.pop_back();
}
if (stk.empty()) {
LP[i] = -1;
LS[i] = H[i] * (i + 1);
} else {
LP[i] = stk.back();
LS[i] = H[i] * (i - LP[i]) + LS[LP[i]];
}
stk.push_back(i);
}
vector<int> RS(N), RP(N); stk.clear();
for (int i = N - 1; i >= 0; i--) {
while (!stk.empty() && H[stk.back()] <= H[i]) {
stk.pop_back();
}
if (stk.empty()) {
RP[i] = N;
RS[i] = H[i] * (N - i);
} else {
RP[i] = stk.back();
RS[i] = H[i] * (RP[i] - i) + RS[RP[i]];
}
stk.push_back(i);
}
vector<int> lg(N + 1);
for (int i = 2; i <= N; i++) {
lg[i] = lg[i / 2] + 1;
}
vector st(N, vector<int>(lg[N] + 1));
for (int i = 0; i < N; i++) {
st[i][0] = LS[i] + RS[i] - H[i];
}
for (int j = 0; j < lg[N]; j++) {
for (int i = 0; i + (2 << j) <= N; i++) {
st[i][j + 1] = min(st[i][j], st[i + (1 << j)][j]);
}
}
auto query = [&](int l, int r) {
int k = lg[r - l];
return min(st[l][k], st[r - (1 << k)][k]);
};
vector<ll> ans(Q, 1e18);
for (int q = 0; q < Q; q++) {
for (int a = 1; a <= 20; a++) {
for (int b = 1; b <= 20; b++) {
int pa = RC[L[q]][a];
int pb = LC[R[q]][b];
if (pa > R[q] || pb < L[q] || LP[pa] >= L[q] || RP[pb] <= R[q]) {
continue;
}
int l = max(pa, LP[pb] + 1);
int r = min(pb, RP[pa] - 1);
if (l > r) {
continue;
}
int s = query(l, r + 1);
if (LP[pa] == -1) {
s -= a * L[q];
} else {
s -= a * (L[q] - 1 - LP[pa]);
s -= LS[LP[pa]];
}
if (RP[pb] == N) {
s -= b * (N - 1 - R[q]);
} else {
s -= b * (RP[pb] - 1 - R[q]);
s -= RS[RP[pb]];
}
ans[q] = min(ans[q], 1ll * s);
}
}
}
return ans;
}
