#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<ll> minimum_costs(vector<int> h, vector<int> L, vector<int> R) {
int n = h.size();
int q = L.size();
vector<ll> ans;
for (int curr = 0; curr < q; curr++) {
int l = L[curr];
int r = R[curr];
vector<ll> dpl(n, 0), dpr(n, 0);
stack<pair<int, int>> st;
for (int i = l; i <= r; i++) {
int cov = 1;
while (!st.empty() && h[st.top().first] <= h[i]) {
cov += st.top().second;
st.pop();
}
dpl[i] = (ll)cov * (ll)h[i];
if (!st.empty()) dpl[i] += dpl[st.top().first];
st.push({i, cov});
}
while (!st.empty()) st.pop();
for (int i = r; i >= l; i--) {
int cov = 1;
while (!st.empty() && h[st.top().first] <= h[i]) {
cov += st.top().second;
st.pop();
}
dpr[i] = (ll)cov * (ll)h[i];
if (!st.empty()) dpr[i] += dpr[st.top().first];
st.push({i, cov});
}
ll fin = dpl[l] + dpr[r];
for (int i = l; i <= r; i++) fin = min(fin, dpl[i] + dpr[i] - (ll)h[i]);
ans.push_back(fin);
}
return ans;
}
