#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
using ll = long long;
const ll INF = 1LL<<60;
const int mxN = 75e4;
const int offset = 2<<__lg(mxN-1);
int n, q;
vector<int> h;
ll val[2*offset];
void upd(int i, ll x) {
i += offset;
val[i] += x;
while (i /= 2) val[i] = min(val[2*i], val[2*i+1]);
}
ll qry(int i, int j) {
i += offset-1;
j += offset+1;
ll ans = INF;
while (i+1 < j) {
if (i%2 == 0) ans = min(ans, val[i+1]);
if (j%2 == 1) ans = min(ans, val[j-1]);
i /= 2, j /= 2;
}
return ans;
}
void insert(int i) {
for (int j = i, mx = h[i]; j < n; ++j) {
mx = max(mx, h[j]);
upd(j, mx);
}
for (int j = i-1, mx = h[i]; j >= 0; --j) {
mx = max(mx, h[j]);
upd(j, mx);
}
}
void erase(int i) {
for (int j = i, mx = 0; j < n; ++j) {
mx = max(mx, h[j]);
upd(j, -mx);
}
for (int j = i-1, mx = 0; j >= 0; --j) {
mx = max(mx, h[j]);
upd(j, -mx);
}
}
ll solve(int L, int R) {
static int CL = 0, CR = -1;
while (CR < R) insert(++CR);
while (CL > L) insert(--CL);
while (CR > R) erase(CR--);
while (CL < L) erase(CL++);
return qry(L, R);
}
vector<ll> minimum_costs(vector<int> h_, vector<int> l, vector<int> r) {
h = h_;
n = (int)h.size();
q = (int)l.size();
vector<ll> ans(q);
const int R = sqrt(n);
vector<int> s(q);
iota(s.begin(), s.end(), 0);
sort(s.begin(), s.end(), [&](int i, int j) -> bool {
if (l[i]/R != l[j]/R) return l[i]/R < l[j]/R;
return (r[i]>r[j])^l[i];
});
for (int qq : s)
ans[qq] = solve(l[qq], r[qq]);
return ans;
}
