#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];
ll lazy[offset];
int push(int I, int l, int r) {
if (lazy[I]) {
val[2*I] += lazy[I];
val[2*I+1] += lazy[I];
if (2*I < offset) {
lazy[2*I] += lazy[I];
lazy[2*I+1] += lazy[I];
}
lazy[I] = 0;
}
return l + (r-l+1)/2;
}
ll qry(int i, int j, int I = 1, int l = 0, int r = mxN-1) {
if (i > r || j < l) return INF;
if (i <= l && j >= r) return val[I];
int mid = push(I, l, r);
ll ans = INF;
if (i < mid) ans = min(ans, qry(i, j, 2*I, l, mid-1));
if (j >= mid) ans = min(ans, qry(i, j, 2*I+1, mid, r));
return ans;
}
void upd(int i, int j, ll x, int I = 1, int l = 0, int r = mxN-1) {
if (i > r || j < l) return;
if (i <= l && j >= r) {
val[I] += x;
if (I < offset) lazy[I] += x;
return;
}
int mid = push(I, l, r);
if (i < mid) upd(i, j, x, 2*I, l, mid-1);
if (j >= mid) upd(i, j, x, 2*I+1, mid, r);
val[I] = min(val[2*I], val[2*I+1]);
}
void insert(int i) {
for (int j = i, mx = h[i]; j < n; ++j) {
mx = max(mx, h[j]);
upd(j, j, mx);
}
for (int j = i-1, mx = h[i]; j >= 0; --j) {
mx = max(mx, h[j]);
upd(j, j, mx);
}
}
void erase(int i) {
for (int j = i, mx = 0; j < n; ++j) {
mx = max(mx, h[j]);
upd(j, j, -mx);
}
for (int j = i-1, mx = 0; j >= 0; --j) {
mx = max(mx, h[j]);
upd(j, 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;
}
