#include <bits/stdc++.h>
#include "meetings.h"
#define pb push_back
#define pii pair<int, int>
#define X first
#define Y second
using namespace std;
void print(vector<int> a){
for(auto i : a)cout << i << ' ';
cout << '\n';
}
void pp(vector<pii> a){
for(auto i : a)cout << i.X << ' '<< i.Y<<'|';
cout << '\n';
}
long long comp(int l, int r, vector<int>& H){
vector<int> ri, le;
vector<pii> st;
ri.assign(H.size(), 0);
le.assign(H.size(), 0);
int cur = 0;
for(int i = l; i<= r; i++){
int tmp = 1;
while(1){
if(st.size() == 0 || st.back().X > H[i]){
st.pb({H[i], tmp});
cur+= H[i]*tmp;
le[i] = cur;
break;
}else{
cur-=st.back().X * st.back().Y;
tmp+=st.back().Y;
st.pop_back();
}
}
}
st.clear();
cur = 0;
for(int i =r; i>=l; i--){
int tmp = 1;
while(1){
if(st.size() == 0 || st.back().X > H[i]){
st.pb({H[i], tmp});
cur+= H[i]*tmp;
ri[i] = cur;
break;
}else{
cur-=st.back().X * st.back().Y;
tmp+=st.back().Y;
st.pop_back();
}
}
}
//print(le);
//print(ri);
long long ret = 1e17;
for(int i = l; i < r; i++){
ret = min(ret, (long long)(le[i]+ri[i+1]));
}
return ret;
}
vector<long long> minimum_costs(vector<int> H, vector<int> L,
vector<int> R) {
int Q = L.size();
vector<long long> C(Q);
for (int j = 0; j < Q; ++j) {
C[j] = comp(L[j], R[j], H);
}
return C;
}
