#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define bug(x) cout << #x << " " << x << endl;
const ll inf = 1e9 + 10;
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
int n = H.size(), q = L.size();
vector<ll> resp(q);
vector<ll> respL(n);
for( int i = 0; i < q; i++ ){
int l = L[i], r = R[i];
resp[i] = inf*inf;
stack<pair<int,ll>> pilha;
pilha.push({ l - 1, inf });
ll sum = 0;
for( int j = l; j <= r; j++ ){
while( pilha.top().second <= H[j] ){
auto [id, v] = pilha.top(); pilha.pop();
sum -= 1LL*v*abs(id - pilha.top().first);
}
sum += 1LL*H[j]*abs(j - pilha.top().first);
pilha.push({ j, H[j] });
respL[j] = sum;
}
while( !pilha.empty() ) pilha.pop();
pilha.push({ r + 1, inf });
sum = 0;
for( int j = r; j >= l; j-- ){
while( pilha.top().second <= H[j] ){
auto [id, v] = pilha.top(); pilha.pop();
sum -= 1LL*v*abs(id - pilha.top().first);
}
sum += 1LL*H[j]*abs(j - pilha.top().first);
pilha.push({ j, H[j] });
resp[i] = min( resp[i], sum + respL[j] - H[j] );
}
}
return resp;
}
