#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e6 + 100;
const int maxl = 20;
int n;
ll a[maxn];
int lg[maxn];
int p[maxl][maxn];
ll d[maxn * 4];
ll t[maxn * 4];
bool c[maxn * 4];
vector<ll> ans;
vector<tuple<int, int, int>> g[maxn];
int C;
int f(int i, int j){
if(C){
if(a[i] >= a[j]) return i;
return j;
} else{
if(a[i] > a[j]) return i;
return j;
}
} int mx(int l, int r){
int k = lg[r - l + 1];
return f(p[k][l], p[k][r-(1<<k)+1]);
}
void pre(int v, ll a, ll b, bool C){
if(C) d[v] = t[v] = 0, c[v] = 1;
d[v] += a; t[v] += b;
} void push(int v, int tl, int tr){
if(tl == tr) return;
int mid = (tl + tr) >> 1;
pre(v<<1, d[v], t[v], c[v]);
pre(v<<1|1, d[v] + (mid - tl + 1) * t[v], t[v], c[v]);
d[v] = t[v] = c[v] = 0;
} void upd(int l, int r, ll a, ll b, bool c, int v = 1, int tl = 1, int tr = n){
if(tl > r || tr < l) return;
if(l <= tl && tr <= r) pre(v, a + (tl - l) * b, b, c);
else{ push(v, tl, tr);
int mid = (tl + tr) >> 1;
upd(l, r, a, b, c, v<<1, tl, mid);
upd(l, r, a, b, c, v<<1|1, mid+1, tr);
}
} ll get(int i, int v = 1, int tl = 1, int tr = n){
if(tl == tr) return d[v];
else{ push(v, tl, tr);
int mid = (tl + tr) >> 1;
if(i <= mid) return get(i, v<<1, tl, mid);
else return get(i, v<<1|1, mid+1, tr);
}
}
void calc(int l = 1, int r = n){
if(l > r) return;
int v = mx(l, r);
calc(l, v - 1); calc(v + 1, r);
// cout << l << ' ' << r << ' ' << v << ":\n";
for(auto [i, tl, tr]: g[v]){
// cout << i << ' ' << tl << ' ' << tr << ' ' << get(tr) + (v - tl + 1) * a[v] << endl;
ans[i] = min(ans[i], get(tr) + (v - tl + 1) * a[v]);
}
if(l < v) upd(v, v, get(v-1) + a[v], 0, 1);
else upd(v, v, a[v], 0, 1);
ll val = get(v), k = v;
// cout << v << ' ' << l << ' ' << r << ":\n";
for(int tl = v + 1, tr = r; tl <= tr;){
int mid = (tl + tr) >> 1;
// cout << mid << ' ' << val + (mid - v) * a[v] << ' ' << get(mid) + (v - l + 1) * a[v] << '\n';
if(val + (mid - v) * a[v] > get(mid) + (v - l + 1) * a[v]) tr = mid - 1;
else tl = mid + 1, k = mid;
} upd(v + 1, k, val + a[v], a[v], 1);
upd(k + 1, r, (v - l + 1) * a[v], 0, 0);
}
void calc(vector<int> A, vector<int> L, vector<int> R){
fill(d, d + maxn * 4, 0);
fill(t, t + maxn * 4, 0);
fill(c, c + maxn * 4, 0);
n = A.size();
for(int i = 1; i <= n; i++){
a[i] = A[i-1];
p[0][i] = i;
g[i].clear();
if(i > 1) lg[i] = lg[i >> 1] + 1;
} for(int k = 1; k < maxl; k++){
for(int i = 1; i + (1<<k) - 1 <= n; i++){
p[k][i] = f(p[k-1][i], p[k-1][i+(1<<(k-1))]);
}
} for(int i = 0; i < L.size(); i++){
g[mx(L[i], R[i])].push_back({i, L[i], R[i]});
}
calc();
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R) {
ans = vector<ll>(L.size(), 1e18);
for(int &x: L) x++;
for(int &x: R) x++;
calc(H, L, R); C = 1;
reverse(H.begin(), H.end());
for(int &x: L) x = (n - x + 1);
for(int &x: R) x = (n - x + 1);
swap(L, R);
calc(H, L, R);
return ans;
}
