#include "meetings.h"
#include<bitset>
#include<compare>
#include<functional>
#include<tuple>
#include<utility>
#include<cstring>
#include<string>
#include<deque>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<unordered_map>
#include<unordered_set>
#include<vector>
#include<iterator>
#include<ranges>
#include<algorithm>
#include<random>
#include<fstream>
#include<iostream>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long int ll;
typedef long double ld;
#define mp make_pair
#define pb push_back
#define eb emplace_back
vector<pair<ll,ll> > dq, pa;
ll aj[750005][2], l[750005], r[750005], root, h[750005], ans[750005];
struct node{
ll s, e, m, lazy, vm, vc;
node *l, *r;
node(ll _s, ll _e): s(_s), e(_e), m((_s+_e)/2), lazy(0), vm(0), vc(0){
if(s!=e){
l = new node(s,m);
r = new node(m+1, e);
}
}
void propo(){
if(lazy){
l->vc += lazy;
r->vc += lazy;
l->lazy += lazy;
r->lazy += lazy;
lazy = 0;
}
}
void update(ll x,ll y, ll nm, ll nc){
if(s==x&&y==e){
if((vm|vc)==0){
vm = nm;
vc = nc;
return;
}
if(nm*m+nc < vm*m+vc){
swap(nm, vm);
swap(vc, nc);
}
if(s!=e){
if(vm > nm)r->update(m+1, e, nm, nc);
if(vm < nm)l->update(s, m, nm, nc);
}
return;
}
propo();
if(y<=m)l->update(x, y, nm, nc);
else if(x>m)r->update(x, y, nm, nc);
else{
l->update(x, m, nm, nc);
r->update(m+1, y, nm, nc);
}
}
void add(ll x,ll y, ll v){
if(s==x&&e==y){
lazy+=v;
vc+=v;
return;
}
propo();
if(y<=m)l->add(x, y, v);
else if(x>m)r->add(x, y, v);
else{
l->add(x, m, v);
r->add(m+1, y, v);
}
}
ll query(ll x){
ll a = 2e9;
if(vm | vc){
a = vm*x+vc;
}
if(s==e)return a;
if(x<=m)return min(a, l->query(x));
else return min(a, r->query(x));
}
} *rootS, *rootP;
vector<tuple<ll,ll, ll> > v, qn[750005];
vector<pair<ll,ll> > dq2;
void dfs(ll x){
ll a = 0, b = 0;
if(~aj[x][0]){
dfs(aj[x][0]);
a = rootP->query(x-1);
}
if(~aj[x][1]){
dfs(aj[x][1]);
b = rootS->query(x+1);
}
//cout<<x<<endl;
for(auto [ql, qr, q]:qn[x]){
// cout<<ql<<" "<<qr<<" "<<q<<endl;
ans[q] = min(((qr>x)?rootP->query(qr):0) + (x-ql+1)*h[x],((ql<x)? rootS->query(ql):0)+(qr-x+1)*h[x]);
}
rootS->add(l[x], x, (r[x] - x+1)*h[x]);
if(x>l[x])rootS->add(x, x, (x-l[x])*h[x]);
rootP->add(x, r[x], (x - l[x]+1)*h[x]);
if(r[x]>x)rootP->add(x, x, (r[x] - x)*h[x]);
rootS->update(l[x], x, -h[x], b+(x+1)*h[x]);
rootP->update(x, r[x], h[x], a+(1-x)*h[x]);
}
vector<long long> minimum_costs(vector<int> H, vector<int> L,
vector<int> R) {
int Q = L.size();
vector<long long> C(Q);
int n = H.size();
ll i,j,k,a,b,c,x,y,z;
memset(aj, -1, sizeof(aj));
for(i=0;i<Q;i++){
v.eb(R[i], L[i], i);
}
sort(all(v));
ll cur = 0;
for(i=0;i<n;i++){
h[i] = H[i];
pa.eb(2e9, -1);
auto it = mp((ll)H[i], i);
while(dq.size()&&dq.back() <= it)dq.pop_back();
if(dq.size()){
pa[i] = dq.back();
l[i] = dq.back().second+1;
}else l[i] = 0;
dq.pb(it);
while(dq2.size()&&dq2.back().second<=h[i])dq2.pop_back();
dq2.pb(mp(i, h[i]));
while(cur<Q&&get<0>(v[cur])==i){
a = lower_bound(dq2.begin(), dq2.end(), mp(get<1>(v[cur]), -1ll)) - dq2.begin();
qn[dq2[a].first].eb(get<1>(v[cur]), get<0>(v[cur]), get<2>(v[cur]));
cur++;
}
}
dq.clear();
for(i=n-1;i>=0;i--){
auto it = mp((ll)H[i], i);
while(dq.size()&&dq.back() <= it)dq.pop_back();
if(dq.size()){
pa[i] = min(dq.back(), pa[i]);
r[i] = dq.back().second-1;
}else r[i] = n-1;
dq.pb(it);
}
for(i=0;i<n;i++){
if(pa[i].second==-1)root = i;
else{
aj[pa[i].second][pa[i].second < i] = i;
}
}
rootP = new node(0, n-1);
rootS = new node(0, n-1);
dfs(root);
for(i=0;i<Q;i++)C[i] = ans[i];
return C;
}
