#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
#define out(o) cout << o
vector<int> H;
long long mono_query(int l, int r) {
vector<long long> left;
stack<pair<int, int>> st;
st.push({H[l], 1});
left.push_back((long long) H[l]);
long long cur = H[l];
for (int j = l + 1; j <= r; j++) {
int change = 1;
while (!st.empty() && st.top().first <= H[j]) {
change += st.top().second;
cur -= ((long long) (st.top().first)) * ((long long) (st.top().second));
st.pop();
}
st.push({H[j], change});
cur += ((long long) (H[j])) * ((long long) (change));
left.push_back(cur);
}
while (!st.empty()) st.pop();
st.push({H[r], 1});
vector<long long> right;
right.push_back((long long) H[r]);
cur = H[r];
for (int j = r - 1; j >= l; j--) {
int change = 1;
while (!st.empty() && st.top().first <= H[j]) {
change += st.top().second;
cur -= ((long long) (st.top().first)) * ((long long) (st.top().second));
st.pop();
}
st.push({H[j], change});
cur += ((long long) (H[j])) * ((long long) (change));
right.push_back(cur);
}
reverse(right.begin(), right.end());
long long here = 1e18;
for (int j = 0; j < r - l + 1; j++) here = min(here, left[j] + right[j] - ((long long) H[l + j]));
return here;
}
struct segtree {
int N;
vector<long long> initial;
vector<long long> tree;
bool op;
segtree() {}
segtree(int NI, vector<long long> initialI, bool opI) {
N = NI;
for (int i = 0; i < N; i++) initial.push_back(initialI[i]);
tree.resize(4 * N, op? -1e18: 1e18);
op = opI;
}
void build(int v, int l, int r) {
if (l == r) tree[v] = initial[l];
else {
int middle = (l + r) / 2;
build(2 * v, l, middle);
build(2 * v + 1, middle + 1, r);
tree[v] = op? max(tree[2 * v], tree[2 * v + 1]): min(tree[2 * v], tree[2 * v + 1]);
}
}
void upd(int v, int i, int x, int l, int r) {
if (l == r) tree[v] = x;
else {
int middle = (l + r) / 2;
if (i <= middle) upd(2 * v, i, x, l, middle);
else upd(2 * v + 1, i, x, middle + 1, r);
tree[v] = op? max(tree[2 * v], tree[2 * v + 1]): min(tree[2 * v], tree[2 * v + 1]);
}
}
long long query(int v, int ql, int qr, int l, int r) {
if (ql <= l && r <= qr) return tree[v];
if (qr < l || r < ql) return op? -1e18: 1e18;
int middle = (l + r) / 2;
long long left = query(2 * v, ql, qr, l, middle);
long long right = query(2 * v + 1, ql, qr, middle + 1, r);
return op? max(left, right): min(left, right);
}
};
vector<vector<int>> occ;
vector<segtree> trees;
segtree rmax;
map<pair<int, int>, long long> memo;
long long fast_query(int l, int r) {
if (memo.find({l, r}) != memo.end()) return memo[{l, r}];
if (l > r) return 0;
int N = rmax.N;
long long maxi = rmax.query(1, l, r, 0, N - 1);
long long add = (r - l + 1) * maxi;
int afterl = lower_bound(occ[maxi].begin(), occ[maxi].end(), l) - occ[maxi].begin();
int afterr = upper_bound(occ[maxi].begin(), occ[maxi].end(), r) - occ[maxi].begin();
afterr--;
int afterli = occ[maxi][afterl];
int afterri = occ[maxi][afterr];
long long answer = min(maxi * (afterri - l + 1) + fast_query(afterri + 1, r), fast_query(l, afterli - 1) + maxi * (r - afterli + 1));
if (afterl != afterr) {
afterr--;
//out(trees[maxi - 1].query(1, l, occ[maxi][afterr], 0, N - 1));
answer = min(answer, trees[maxi - 1].query(1, l, occ[maxi][afterr], 0, N - 1) + add);
}
return memo[{l, r}] = answer;
}
vector<long long> minimum_costs(vector<int> HI, vector<int> L, vector<int> R) {
int N = HI.size();
int Q = L.size(); // = R.size()
for (int i = 0; i < N; i++) H.push_back(HI[i]);
if (max(N, Q) <= 5000) {
// subtasks 1 and 2
vector<long long> ans;
for (int i = 0; i < Q; i++) {
int l = L[i];
int r = R[i];
long long here = mono_query(l, r);
ans.push_back(here);
}
return ans;
} else {
// subtasks 3 and 4
vector<long long> HL;
for (int i = 0; i < N; i++) HL.push_back((long long) H[i]);
rmax.initial = HL;
rmax.N = N;
rmax.op = true;
rmax.tree.resize(4 * N, -1e18);
rmax.build(1, 0, N - 1);
occ.resize(21);
for (int i = 0; i < N; i++) occ[H[i]].push_back(i);
for (int i = 1; i <= 20; i++) {
int s = occ[i].size();
vector<long long> queries(N, 1e18);
for (int j = 0; j < s; j++) {
for (int k = occ[i][j] + 1; k < (j == s - 1? N: occ[i][j + 1]); k++) {
if (H[k] > i) break;
long long here = fast_query(occ[i][j] + 1, k);
if (j < s - 1 && k == occ[i][j + 1] - 1) queries[occ[i][j]] = here - i * (occ[i][j + 1] - occ[i][j] - 1);
}
for (int k = occ[i][j] - 1; k >= (j == 0? 0: occ[i][j - 1] + 1); k--) {
if (H[k] > i) break;
fast_query(k, occ[i][j] - 1);
}
}
segtree tree(N, queries, false);
tree.build(1, 0, N - 1);
trees.push_back(tree);
}
vector<long long> ans;
for (int i = 0; i < Q; i++) {
int l = L[i];
int r = R[i];
long long here = fast_query(l, r);
ans.push_back(here);
}
return ans;
}
}
