#include "meetings.h"
using namespace std;
#define ALL(x) begin(x),end(x)
#define pb push_back
#define F first
#define S second
// #define int long long
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
typedef vector<vb> vvb;
template<typename T>
T meq(T& a, T b){
return a=max(a,b);
}
#define D 20
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R) {
int Q = L.size();
int n = H.size();
std::vector<long long> C(Q);
vi lg(n+1);
lg[0]=-10000000;lg[1]=0;
for (int i=2;i<=n;i++)lg[i]=lg[i/2]+1;
vvii mxs(D, vii(n)); // height, ind
for (int i=0;i<n;i++)mxs[0][i]={H[i], i};
for (int d=1;d<D;d++){
for (int i=0;i<n;i++){
mxs[d][i]=mxs[d-1][i];
if(i+(1<<(d-1))<n)meq(mxs[d][i],mxs[d-1][i+(1<<(d-1))]);
}
}
auto solve = [&](auto&& self, int l, int r) -> ll {
int len = r-l;
if (len==0)return 0;
if (len==1)return H[l];
int d = lg[len];
auto [mx, pmx] = max(mxs[d][l], mxs[d][r-(1<<d)]);
return min(
ll(mx)*ll(pmx-l+1) + self(self, pmx+1, r),
ll(mx)*ll(r-pmx) + self(self, l, pmx)
);
};
for (int j = 0; j < Q; ++j) {
C[j] = solve(solve, L[j], R[j]+1);
}
return C;
}
