#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#undef int
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,std::vector<int> R) {
#define int long long
int q = L.size();
int n = H.size();
vector< int > firstLeft(n,-1);
vector< int > firstRight(n,numeric_limits<int>::max());
vector< pair<int,int> > stack;
for(int i = n-1; i >= 0; i--){
while(!stack.empty() && stack.back().first < H[i]){
stack.pop_back();
}
if(!stack.empty()){
firstRight[i] = stack.back().second;
}
stack.push_back({H[i],i});
}
stack.clear();
for(int i = 0; i < n; i++){
while(!stack.empty() && stack.back().first < H[i]){
stack.pop_back();
}
if(!stack.empty()){
firstLeft[i] = stack.back().second;
}
stack.push_back({H[i],i});
}
vector< int > ans(q);
for(int i = 0; i < q; i++){
int best = numeric_limits<int>::max();
for(int j = L[i]; j <= R[i]; j++){
if(j > L[i] && H[j] == H[j-1]) continue;
int tot = -H[j]; //AVOID COUNTING TWICE
int currLeft = j;
int currRight = j;
int currCost = H[j];
while(firstLeft[currLeft] >= L[i]){
tot += (currLeft-firstLeft[currLeft])*currCost;
currLeft = firstLeft[currLeft];
currCost = H[currLeft];
}
tot += (currLeft-L[i]+1)*currCost;
currCost = H[j];
//cout << "LEFT " << tot << endl;
while(firstRight[currRight] <= R[i]){
//cout << "RIGHTE " << firstRight[currRight] << ' ' << currRight << endl;
tot += (firstRight[currRight]-currRight)*currCost;
currRight = firstRight[currRight];
currCost = H[currRight];
//cout << tot << endl;
}
tot += (R[i] - currRight+1)*currCost;
if(tot < best){
//cout << tot << ' ' << j << endl;
best = tot;
}
}
//cout << "done" << endl;
ans[i] = best;
}
return ans;
}
