#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R) {
int n = (int)H.size(),m = (int)L.size();
vector<vector<int>>sparce(n,vector<int>(25));
for (int i = 0;i<n;++i)sparce[i][0] = H[i];
for (int i = 1;i<25;++i){
for (int j = 0;j + (1<<(i - 1))< n;++j){
sparce[j][i] = max(sparce[j][i - 1],sparce[j + (1<<(i - 1))][i - 1]);
}
}
auto getmax = [&](int l,int r){
int lg = 32 - __builtin_clz(r - l + 1) - 1;
return max(sparce[l][lg],sparce[r - (1<<lg) + 1][lg]);
};
vector<long long>ans(m);
for (int i = 0;i<m;++i){
long long cur_ans = LLONG_MAX;
for (int j = L[i];j<=R[i];++j){
long long pos = 0;
for (int k = L[i];k<j;++k){
pos+=getmax(k,j);
}
for (int k = R[i];k>j;--k){
pos+=getmax(j,k);
}
pos+=H[j];
cur_ans = min(cur_ans,pos);
}
ans[i] = cur_ans;
}
return ans;
}
