#include "meetings.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
const long long INF = 1e17;
typedef long long ll;
const ll MOD = (ll)1e9+7;
#define P pair
#define F first
#define pb push_back
#define V vector
#define all(v) v.begin(), v.end()
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R) {
ll q=(ll)L.size();
ll n=(ll)H.size();
V<ll>C;
V<ll>h(n+1);
for (ll i=1;i<=n;i++) {
h[i]=H[i-1];
}
V<ll>idl(n+1,0),idr(n+1,n+1);
for (ll i=1;i<=n;i++) {
for (ll j=i-1;j>=1;j--) {
if (h[j]>=h[i]) {
idl[i]=j;
break;
}
}
for (ll j=i+1;j<=n;j++) {
if (h[j]>=h[i]) {
idr[i]=j;
break;
}
}
}
for (ll i=0;i<q;i++) {
ll l=L[i]+1,r=R[i]+1;
V<ll>dpl(n+2,0),dpr(n+2);
for (ll j=l;j<=r;j++) {
ll id=max(idl[j],l-1);
dpl[j]+=dpl[id]+(j-id)*h[j];
}
for (ll j=r;j>=l;j--) {
ll id=min(idr[j],r+1);
dpr[j]+=dpr[id]+(id-j)*h[j];
}
ll ans=LLONG_MAX;
for (ll j=l;j<=r;j++) {
ans=min(ans,dpl[j]+dpr[j]-h[j]);
}
C.pb(ans);
}
return C;
}
