#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
//#define int long long
using i64 = long long;
template <class F, class _S>
bool chmin(F &u, const _S &v){
bool flag = false;
if ( u > v ){
u = v; flag |= true;
}
return flag;
}
template <class F, class _S>
bool chmax(F &u, const _S &v){
bool flag = false;
if ( u < v ){
u = v; flag |= true;
}
return flag;
}
const i64 inf = 1e15;
vector <int> h;
int n;
struct Info{
i64 best;
int l, r, x, len;
Info *lf, *rg;
Info(int l = 0, int r = -1) : best(0), l(l), r(r), len(r - l + 1), lf(NULL), rg(NULL) {}
};
struct SegTree{
Info *root = new Info();
SegTree(){
root = build(0, n - 1);
}
Info *build(int l, int r){
Info *v = new Info(l, r);
if ( l <= r ){
int top = 0;
for ( int i = l; i <= r; i++ ){
chmax(top, h[i]);
}
vector <int> ids;
for ( int i = l; i <= r; i++ ){
if ( h[i] == top ) ids.pb(i);
}
v -> x = ids[(int)ids.size() / 2];
Info *lf = build(l, v -> x - 1);
Info *rg = build(v -> x + 1, r);
v -> best = min(lf -> best + h[v -> x] * 1LL * rg -> len,
rg -> best + h[v -> x] * 1LL * lf -> len) + top;
v -> lf = lf;
v -> rg = rg;
}
return v;
}
Info *qry(Info *v, int l, int r){
Info *ret = new Info();
if ( v -> l > r || v -> r < l ) return ret;
if ( v -> l >= l && v -> r <= r ){
return v;
}
if ( !v -> lf ) return qry(v -> rg, l, r);
if ( !v -> rg ) return qry(v -> lf, l, r);
Info *lf = qry(v -> lf, l, r);
Info *rg = qry(v -> rg, l, r);
int cnt = (l <= v -> x && r >= v -> x);
ret -> best = min(lf -> best + h[v -> x] * 1LL * rg -> len,
rg -> best + h[v -> x] * 1LL * lf -> len) + cnt * h[v -> x];
ret -> len = lf -> len + rg -> len + cnt;
return ret;
}
i64 qry(int l, int r){
return qry(root, l, r) -> best;
}
};
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R) {
int q = L.size(); n = H.size(); h = H;
// subtask #4
SegTree seg;
vector <i64> ans(q);
for ( int i = 0; i < q; i++ ){
ans[i] = seg.qry(L[i], R[i]);
}
return ans;
}
