#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
const int INF = 1e9;
const int N1 = 5005, N2 = 1e5 + 5, K = 21;
ll lp[N1][N1], rp[N1][N1];
int n, q;
vector<int> a;
vector<ll> slow(vector<int> L, vector<int> R) {
for (int i = 0; i < n; i++) {
ll cur = 0;
int mx = a[i];
for (int j = i - 1; j >= 0; j--) {
mx = max(mx, a[j]);
cur += mx;
lp[j][i] = cur;
}
cur = 0;
mx = a[i];
for (int j = i + 1; j < n; j++) {
mx = max(mx, a[j]);
cur += mx;
rp[i][j] = cur;
}
}
vector<ll> ans(q);
for (int i = 0; i < q; i++) {
ll mn = INF;
for (int j = L[i]; j <= R[i]; j++) {
mn = min(mn, lp[L[i]][j] + rp[j][R[i]] + a[j]);
}
ans[i] = mn;
}
return ans;
}
struct Node {
int mx, lp[K], rp[K], val[K][K];
Node() {
for (int i = 0; i < K; i++) {
for (int j = 0; j < K; j++) {
val[i][j] = INF;
}
}
fill(lp, lp + K, 0);
fill(rp, rp + K, 0);
mx = 0;
}
} t[N2 * 4];
void upd(int &a, int b) {
a = min(a, b);
}
Node operator + (Node a, Node b) {
Node c;
c.mx = max(a.mx, b.mx);
for (int i = 0; i < K; i++) {
c.rp[i] = b.rp[i] + a.rp[max(i, b.mx)];
c.lp[i] = a.lp[i] + b.lp[max(i, a.mx)];
}
for (int i = 0; i < K; i++) {
for (int j = 0; j < K; j++) {
upd(c.val[i][max(j, b.mx)], a.val[i][j] + b.lp[j]);
upd(c.val[max(i, a.mx)][j], b.val[i][j] + a.rp[i]);
}
}
return c;
}
void build(int v, int L, int R) {
if (L == R) {
t[v].val[a[L]][a[L]] = a[L];
for (int i = 0; i <= a[L]; i++)
t[v].lp[i] = t[v].rp[i] = a[L];
for (int i = a[L] + 1; i < K; i++) {
t[v].lp[i] = t[v].rp[i] = i;
}
t[v].mx = a[L];
}
else {
int m = (L + R) >> 1;
build(v * 2, L, m);
build(v * 2 + 1, m + 1, R);
t[v] = t[v * 2] + t[v * 2 + 1];
}
// cout << L << " " << R << " :\n";
// for (int i = 0; i < 2; i++) {
// for (int j = 0; j < 2; j++) {
// cout << i << " " << j << " = " << t[v].val[i][j] << "\n";
// }
// }
// cout << "\n\n";
// for (int i = 0; i < 2; i++)
// cout << t[v].lp[i] << " ";
// cout << "\n";
// for (int i = 0; i < 2; i++)
// cout << t[v].rp[i] << " ";
// cout << "\n";
// cout << "\n";
}
Node que(int l, int r, int v, int L, int R) {
if (l > r)
return Node();
if (l == L && r == R)
return t[v];
int m = (L + R) >> 1;
return que(l, min(m, r), v * 2, L, m) +
que(max(m + 1, l), r, v * 2 + 1, m + 1, R);
}
vector<ll> solveWhenLessThan20(vector<int> L, vector<int> R) {
build(1, 0, n - 1);
vector<ll> ans(q, 0);
for (int i = 0; i < q; i++) {
auto res = que(L[i], R[i], 1, 0, n - 1);
int mn = INF;
for (int x = 0; x < K; x++) {
for (int y = 0; y < K; y++) {
mn = min(mn, res.val[x][y]);
}
}
ans[i] = mn;
}
return ans;
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R) {
a = H;
n = a.size(), q = L.size();
if (n < N1 && q < N1) {
return slow(L, R);
}
return solveWhenLessThan20(L, R);
}
