#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fall(i,a,b) for(int i=a;i<=b;i++)
#define rfall(i,a,b) for(int i=a;i>=b;i--)
#define sz(x) (int) x.size()
#define pb push_back
#define all(x) (int)x.size()
const int MAXN=9e4+10;
const ll inf=1e17;
typedef pair<int,int> pii;
int n;
ll peso[MAXN];
vector<ll> v;
ll query(int l,int r){
vector<ll> cost(n);
fall(i,0,n-1) peso[i]=0;
ll cur=0;
stack<int> st;
fall(i,l,r){
cur+=v[i];
peso[i]=1;
while(!st.empty()){
auto x=st.top();
if(v[x]>v[i]) break;
st.pop();
cur+=(v[i]-v[x])*peso[x];
peso[i]+=peso[x];
}
cost[i]=cur;
st.push(i);
}
while(sz(st)) st.pop();
cur=0;
ll ans=inf;
rfall(i,r,l){
peso[i]=1;
while(!st.empty()){
auto x=st.top();
if(v[x]>v[i]) break;
st.pop();
cur+=(v[i]-v[x])*peso[x];
peso[i]+=peso[x];
}
cost[i]+=cur;
cur+=v[i];
st.push(i);
ans=min(ans,cost[i]);
}
return ans;
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,std::vector<int> R) {
n=sz(H);
for(auto u:H) v.pb(u);
vector<ll> ans(sz(L));
fall(j,0,sz(L)-1) ans[j]=query(L[j],R[j]);
return ans;
}
