#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define vi vector<int>
#define ff first
#define ss second
#define ll long long int
#define pii pair<int,int>
const int N = 1e5+100, K = 22;
int rmq[N][K], dp[N][K];
int get(int l, int r){
int k = __lg(r-l+1);
return max(rmq[l][k], rmq[r-(1<<k)+1][k]);
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R) {
int n = H.size();
int q = L.size();
for(int i = 0; i < n; ++i) rmq[i][0] = H[i];
for(int j = 1; j < K; ++j){
for(int i = 0; i + (1<<j) <= n; ++i){
rmq[i][j] = max(rmq[i][j-1], rmq[i+(1<<(j-1))][j-1]);
}
}
vector<ll> C;
for(int _ = 0; _ < q; ++_){
ll ans = 1e18;
for(int i = L[_]; i <= R[_]; ++i){
ll cur = 0;
for(int j = L[_]; j <= R[_]; ++j){
if(i<=j) cur += get(i, j);
else cur += get(j,i);
}
ans=min(ans,cur);
}
C.pb(ans);
}
return C;
}
