#include <bits/stdc++.h>
#include "meetings.h"
#define F first
#define S second
#define SZ(a) ((int)(a).size())
#define PB push_back
#define ALL(a) (a).begin(), (a).end()
using namespace std;
typedef long long ll;
typedef pair<ll, ll> ii;
std::vector<ll> mxh;
int np2;
ll mxque(int a, int b, int i=0, int j=np2, int h=1){
if(a<=i && j<=b)
return mxh[h];
if(j<=a || b<=i)
return 0;
return max(mxque(a,b,i,(i+j)/2,h*2),mxque(a,b,(i+j)/2,j,h*2+1));
}
std::vector<long long> minimum_costs(std::vector<int> h, std::vector<int> l, std::vector<int> r) {
int q = SZ(l), n=SZ(h);
np2=1<<(32-__builtin_clz(n));
mxh.clear();
mxh.resize(np2*2,0);
for(int i=0; i<n; i++)
mxh[i+np2]=h[i];
for(int i=np2-1; i>0; i--)
mxh[i]=max(mxh[2*i],mxh[2*i+1]);
// for(ll x: mxh)
// fprintf(stderr, "%lld\n", x);
std::vector<long long> c(q);
for(int i=0; i<q; i++){
c[i]=LLONG_MAX;
for(int j=l[i]; j<=r[i]; j++){
ll t=0;
for(int k=l[i]; k<=r[i]; k++){
t+=mxque(min(k,j),max(k,j)+1);
// fprintf(stderr, "%lld %d %d\n", t, j, k);
}
c[i]=min(c[i],t);
}
}
return c;
}
