#include "meetings.h"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define all(x) begin(x),end(x)
const int oo = 1e9;
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R) {
int Q = L.size();
int n =H.size();
std::vector<long long> C;
vi l(n);
for(int i=0;i<n;++i) {
l[i]=i-1;
while(l[i]>=0 and H[l[i]]<=H[i]) {
l[i]=l[l[i]];
}
}
vi r(n);
for(int i=n-1;i>=0;--i) {
r[i]=i+1;
while(r[i]<n and H[r[i]]<=H[i]) {
r[i] = r[r[i]];
}
}
for(int i=0;i<Q;++i) {
int ql = L[i],qr = R[i];
vector<ll> dpl(n),dpr(n);
for(int i=ql;i<=qr;++i) {
if(l[i]<ql) {
dpl[i] = (i-ql+1)*ll(H[i]);
} else dpl[i] = (i-l[i])*ll(H[i]) + dpl[l[i]];
}
for(int i=qr;i>=ql;--i) {
if(r[i]>qr) {
dpr[i] = (qr-i+1)*ll(H[i]);
} else dpr[i] = (r[i]-i)*ll(H[i]) + dpr[r[i]];
}
ll ans = 1e18;
for(int i=ql;i<=qr;++i) {
ans=min(ans,dpl[i]+dpr[i]-H[i]);
}
C.push_back(ans);
}
return C;
}
