#include "meetings.h"
#include <stack>
#include <algorithm>
#include <iostream>
using namespace std;
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 q = 0; q < Q; ++q) {
int l = L[q], r = R[q];
vector<long long> ans(r-l+1);
stack<int> st;
// Find answer contributions from left
st.push(l-1);
long long sum = 0;
for (int i = l; i <= r; ++i) {
while (st.top() >= l && H[st.top()] <= H[i]) {
int x = st.top();
st.pop();
sum += (long long)(x-st.top())*(H[i]-H[x]);
}
st.push(i);
sum += H[i];
ans[i-l] += sum;
}
while (!st.empty()) st.pop();
// Find answer contributions from right
st.push(r+1);
sum = 0;
for (int i = r; i >= l; --i) {
while (st.top() <= r && H[st.top()] <= H[i]) {
int x = st.top();
st.pop();
sum += (long long)(st.top()-x)*(H[i]-H[x]);
}
st.push(i);
sum += H[i];
ans[i-l] += sum;
}
while (!st.empty()) st.pop();
// Choose best answer
long long minCost = 1e18;
for (int i = l; i <= r; ++i) {
ans[i-l] -= H[i]; // counted from both sides
minCost = min(minCost, ans[i-l]);
}
C[q] = minCost;
}
return C;
}
