#include "meetings.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define printv(a, b) { \
for(auto pv : a) b << pv << " "; \
b << "\n"; \
}
#define mp make_pair
#define F first
#define S second
#define pob pop_back()
#define iter(a) a.begin(), a.end()
using namespace std;
typedef long long ll;
using pll = pair<ll, ll>;
vector<int> h;
ll solve(int l, int r){
//cerr << "query " << l << " " << r << "\n";
vector<pll> dq;
ll sum = 0;
vector<ll> ans(r - l + 1);
for(int i = l; i <= r; i++){
ll len = 1;
while(!dq.empty() && dq.back().F <= h[i]){
sum -= dq.back().F * dq.back().S;
len += dq.back().S;
dq.pob;
}
sum += h[i] * len;
dq.eb(mp(h[i], len));
//cerr << i << " " << sum << "\n";
ans[i - l] += sum;
}
dq.clear();
sum = 0;
for(int i = r; i >= l; i--){
ll len = 1;
while(!dq.empty() && dq.back().F <= h[i]){
sum -= dq.back().F * dq.back().S;
len += dq.back().S;
dq.pob;
}
sum += h[i] * len;
//cerr << i << " " << sum << "\n";
dq.eb(mp(h[i], len));
ans[i - l] += sum - h[i];
}
return *min_element(iter(ans));
}
vector<ll> minimum_costs(vector<int> H, vector<int> L,
vector<int> R) {
h = H;
int m = L.size();
vector<ll> c(m);
for(int i = 0; i < m; i++) c[i] = solve(L[i], R[i]);
return c;
}
