#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;
Info *lf, *rg;
Info(int l = 0, int r = -1) : best(0), l(l), r(r) {}
};
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 * (r - v -> x),
rg -> best + h[v -> x] * 1LL * (v -> x - l)) + top;
v -> lf = lf;
v -> rg = rg;
}
return v;
}
i64 qry(Info *v, int l, int r){
if ( v -> l > v -> r ) return 0;
int cnt = (v -> x >= l && v -> x <= r);
if ( v -> x >= r ) return qry(v -> lf, l, r) + h[v -> x] * cnt;
if ( v -> x <= l ) return qry(v -> rg, l, r) + h[v -> x] * cnt;
if ( v -> l >= l && v -> r <= r ){
return v -> best;
}
return min(qry(v -> lf, l, r) + h[v -> x] * 1LL * (r - v -> x + 1),
qry(v -> rg, l, r) + h[v -> x] * 1LL * (v -> x - l + 1));
}
i64 qry(int l, int r){ return qry(root, l, r); }
};
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;
}
