#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
ll solve(int n, vector<int> H){
vector<ll> ans(n);
ll v = 0;
stack<pair<ll, int>> st;
for(int i = 0; i < n; i++){
int j = i;
while(!st.empty() && st.top().first < H[i]){
v -= st.top().first * st.top().second;
j -= st.top().second;
st.pop();
}
v += ll(H[i])*(i-j);
ans[i] += v;
v += H[i];
if(!st.empty() && st.top().first == H[i]) st.top().second += i+1-j;
else st.emplace(H[i], i+1-j);
}
v = 0;
st = stack<pair<ll, int>>();
for(int i = n-1; i >= 0; i--){
ans[i] += v;
int j = i;
while(!st.empty() && st.top().first < H[i]){
v -= st.top().first * st.top().second;
j += st.top().second;
st.pop();
}
v += ll(H[i])*(j+1-i);
if(!st.empty() && st.top().first == H[i]) st.top().second += j+1-i;
else st.emplace(H[i], j+1-i);
}
ll mi = INF;
for(int i = 0; i < n; i++) mi = min(mi, ans[i]+H[i]);
return mi;
}
vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
int Q = (int)L.size();
vector<ll> C(Q);
for(int j = 0; j < Q; ++j){
vector<int> h;
for(int k = L[j]; k <= R[j]; k++) h.push_back(H[k]);
C[j] = solve((int)h.size(), h);
}
return C;
}
