#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define TRACE(x) cout << #x << " :: " << x << endl;
#define _ << " " <<
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
typedef long long ll;
const int mxN = 750005;
const int lgN = 19;
const int mxQ = 750005;
int N, Q;
vector<int> H;
struct SparseTable {
int A[mxN][lgN+1];
void init(vector<int>& H) {
FOR(i,0,N-1){ A[i][0] = i; }
FOR(k,1,lgN){
FOR(i,0,N-(1<<k)){
int p = A[i][k-1], q = A[i+(1<<(k-1))][k-1];
A[i][k] = (H[p] > H[q] ? p : q);
}
}
}
int query(int l, int r) {
int k = floor(log2(r-l+1));
int i = A[l][k], j = A[r-(1<<k)+1][k];
return H[i] > H[j] ? i : j;
}
} st;
struct Query { int l, r, i; }; vector<Query> query[mxN];
vector<ll> ans;
ll f(int x, ll m, ll c) { return x*m + c; }
struct SegmentTree {
ll vl[4*mxN], vr[4*mxN], tagM[4*mxN], tagC[4*mxN], add[4*mxN]; bool tag[4*mxN];
int n;
void build(int _n) {
n = _n;
//fill_n(D,4*n,(Node){0,0,0,0,0,0});
}
void replace(int s, int e, int p, ll m, ll c) {
vl[p] = f(s,m,c);
vr[p] = f(e,m,c);
tagM[p] = m;
tagC[p] = c;
add[p] = 0;
tag[p] = true;
}
void addTo(int p, ll v) {
vl[p] += v;
vr[p] += v;
add[p] += v;
}
void prop(int s, int e, int p) {
if (tag[p]) {
if (s != e) {
int mid = (s+e)/2;
replace(s,mid,p<<1,tagM[p],tagC[p]);
replace(mid+1,e,p<<1|1,tagM[p],tagC[p]);
}
tag[p] = false;
}
if (add[p]) {
if (s != e) {
addTo(p<<1,add[p]);
addTo(p<<1|1,add[p]);
}
add[p] = 0;
}
}
void update(int s, int e, int p, int x, int y, ll m, ll c, ll v) {
if (x > y) return;
if (s >= x && e <= y) {
if (f(s,m,c) <= vl[p] + v && f(e,m,c) <= vr[p] + v) return replace(s,e,p,m,c);
if (vl[p] + v < f(s,m,c) && vr[p] + v < f(e,m,c)) return addTo(p,v);
}
int mid = (s+e)/2;
assert(s != e);
prop(s,e,p);
if (mid >= x) update(s,mid,p<<1,x,y,m,c,v);
if (mid < y) update(mid+1,e,p<<1|1,x,y,m,c,v);
vl[p] = vl[p<<1];
vr[p] = vr[p<<1|1];
}
inline void update(int x, int y, ll m, ll c, ll v) { return update(0,N-1,1,x,y,m,c,v); }
ll query(int s, int e, int p, int x) {
if (s == e) {
return vl[p];
} else {
int mid = (s+e)/2;
prop(s,e,p);
if (x <= mid) return query(s,mid,p<<1,x);
else return query(mid+1,e,p<<1|1,x);
}
}
inline ll query(int x) { return query(0,N-1,1,x); }
} fixr, fixl;
void solve(int l, int r) {
if (l > r) return;
int p = st.query(l,r);
solve(l,p-1);
solve(p+1,r);
for (Query q : query[p]) {
ans[q.i] = (ll) (q.r-q.l+1) * H[p];
if (q.l < p) ans[q.i] = min(ans[q.i], fixr.query(q.l) + (ll) (q.r-p+1) * H[p]);
if (q.r > p) ans[q.i] = min(ans[q.i], fixl.query(q.r) + (ll) (p-q.l+1) * H[p]);
}
// f(l,p-1) + (i-p+1) * H[p]
// f(p+1,i) + (p-l+1) * H[p]
ll lv = (p > l ? fixl.query(p-1) : 0);
fixl.update(p,r, H[p], lv+(ll)(-p+1)*H[p], (ll)(p-l+1)*H[p]);
// f(p+1,r) + (p-i+1) * H[p]
// f(i,p-1) + (r-p+1) * H[p]
ll rv = (p < r ? fixr.query(p+1) : 0);
fixr.update(l,p, -H[p], rv+(ll)(p+1)*H[p], (ll)(r-p+1)*H[p]);
}
std::vector<long long> minimum_costs(std::vector<int> _H, std::vector<int> L,
std::vector<int> R) {
H = _H;
N = SZ(H);
Q = SZ(L);
st.init(H);
FOR(i,0,Q-1){
int p = st.query(L[i],R[i]);
query[p].push_back({L[i],R[i],i});
}
ans.assign(Q,0);
fixl.build(N);
fixr.build(N);
solve(0,N-1);
return ans;
}
