#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> h, ql, qr;
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
int n = (int) H.size();
int q = (int) L.size();
h = H; ql = L, qr = R;
const int LOG = 32 - __builtin_clz(n);
vector<vector<int>> spa(LOG);
spa[0] = h;
for (int j = 1; j < LOG; ++j) {
spa[j].resize(n - (1 << j) + 1);
for (int i = 0; i + (1 << j) <= n; ++i) {
spa[j][i] = max(spa[j - 1][i], spa[j - 1][i + (1 << (j - 1))]);
}
}
auto get_max = [&](int l, int r) {
int lg = 31 - __builtin_clz(r - l + 1);
return max(spa[lg][l], spa[lg][r - (1 << lg) + 1]);
};
vector<long long> ret(q);
for (int qind = 0; qind < q; ++qind) {
vector<long long> change(n);
int l = ql[qind], r = qr[qind];
for (int i = l; i < r; ++i) {
if (h[i] < h[i + 1]) {//there's a suffix that will get affected (increase)
int cur = i;
int mx = h[cur];
while (cur >= l && mx < h[i + 1]) {
int lo = l, hi = cur;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (get_max(mid, cur) == mx) {
hi = mid;
} else {
lo = mid + 1;
}
}
change[i] += (long long) (cur - lo + 1) * (h[i + 1] - mx);
if (lo > l) {
cur = lo - 1;
mx = h[lo - 1];
} else {
break;
}
}
}
else if (h[i] > h[i + 1]) {
int cur = i + 1;
int mx = h[cur];
while (cur <= r && mx < h[i]) {
int lo = cur, hi = r;
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
if (get_max(cur, mid) == mx) {
lo = mid;
} else {
hi = mid - 1;
}
}
change[i] -= (long long) (hi - cur + 1) * (h[i] - mx);
if (hi < r) {
cur = hi + 1;
mx = h[hi + 1];
} else {
break;
}
}
}
}
long long init_cost = 0;
int cur = l;
int mx = h[cur];
while (cur <= r) {
int lo = cur, hi = r;
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
if (get_max(cur, mid) == mx) {
lo = mid;
} else {
hi = mid - 1;
}
}
init_cost += (long long) (hi - cur + 1) * mx;
if (hi < r) {
cur = hi + 1;
mx = h[hi + 1];
} else {
break;
}
}
long long mn = init_cost;
for (int i = l; i < r; ++i) {
init_cost += change[i];
mn = min(mn, init_cost);
}
ret[qind] = mn;
}
return ret;
}
