#include <iostream>
#include <vector>
// #include "meetings.h"
using namespace std;
#define ll long long
const ll N = 1<<20, inf = 1e15;
ll Mx[N][20];
vector<long long> Ans;
vector<ll> quer[N];
struct line{
ll m, c, ex;
} seg[2][N<<1];
ll laz[2][N<<1];
string tp[2] = {"pre", "suf"};
ll val(line l, ll x){
return l.m * x + l.c + 1 * inf * (1 - l.ex);
}
bool better(ll x, line l1, line l2){
return (val(l1, x) <= val(l2, x));
}
void Push(ll t, ll cur, ll lc, ll rc){
seg[t][lc].c += laz[t][cur];
seg[t][rc].c += laz[t][cur];
laz[t][cur] = 0;
}
void insert(ll t, line ln, ll cur, ll st, ll en){
ll vl = better(st, ln, seg[t][cur]) + better(en - 1, ln, seg[t][cur]);
if (vl == 2)
seg[t][cur] = ln;
if (vl != 1)
return;
ll lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
Push(t, cur, lc, rc);
insert(t, ln, lc, st, mid);
insert(t, ln, rc, mid, en);
}
void Add1(ll t, line ln, ll l, ll r, ll cur = 1, ll st = 1, ll en = N){
if (cur == 1 and 0)
cout<<tp[t]<<" "<<l<<" "<<r - 1<<" "<<ln.m<<" "<<ln.c<<endl;
if (l >= en or r <= st)
return;
if (l <= st and r >= en){
insert(t, ln, cur, st, en);
return;
}
ll lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
Push(t, cur, lc, rc);
Add1(t, ln, l, r, lc, st, mid);
Add1(t, ln, l, r, rc, mid, en);
}
void Add2(ll t, ll cnst, ll l, ll r, ll cur = 1, ll st = 1, ll en = N){
if (l >= en or r <= st)
return;
if (l <= st and r >= en){
laz[t][cur] += cnst;
seg[t][cur].c += cnst;
return;
}
ll lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
Push(t, cur, lc, rc);
Add2(t, cnst, l, r, lc, st, mid);
Add2(t, cnst, l, r, rc, mid, en);
}
ll get(ll t, ll i, ll cur = 1, ll st = 1, ll en = N){
if (i >= en or i < st)
return inf;
if (en - st == 1)
return val(seg[t][cur], i);
ll lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
Push(t, cur, lc, rc);
return min(min(get(t, i, lc, st, mid), get(t, i, rc, mid, en)), val(seg[t][cur], i));
}
void print(ll n){
cout<<" \\\\\\\\\\\\\\\\\\//////////////////"<<endl;
for (ll i=1;i<=n;i++)
cout<<get(0, i)<<' ';
cout<<'\n';
for (ll i=1;i<=n;i++)
cout<<get(1, i)<<' ';
cout<<'\n'<<endl<<endl<<endl;
}
void solve(vector<int> &H, vector<int> &L, vector<int> &R, int l, int r){
if (r < l)
return;
ll b = 31 - __builtin_clz(r - l + 1), m = Mx[r - (1<<b) + 1][b];
if (H[Mx[l][b]] >= H[m])
m = Mx[l][b];
// cout<<m<<endl;
solve(H, L, R, l, m - 1);
solve(H, L, R, m + 1, r);
// cout<<l<<" "<<r<<" "<<m<<endl;
// print(H.size());
for (ll i : quer[m]){
Ans[i] = min(get(1, L[i]) + (R[i] - m + 1) * H[m], get(0, R[i]) + (m - L[i] + 1) * H[m]);
// cout<<"Ae khalko "<<L[i]<<" "<<R[i]<<" "<<Ans[i]<<" "<<get(1, L[i])<<" "<<get(0, R[i])<<endl;
}
Add2(0, (m - l + 1) * H[m], m+1, r+1);
Add2(1, (r - m + 1) * H[m], l, m);
ll vl = (m > l ? get(0, m - 1) : 0) + H[m];
Add1(0, {0, vl, 1}, m, m + 1);
// print(H.size());
Add1(0, {H[m], vl - m * H[m], 1}, m + 1, r + 1);
// print(H.size());
vl = (r > m ? get(1, m + 1) : 0) + H[m];
Add1(1, {0, vl, 1}, m, m + 1);
// print(H.size());
Add1(1, {-H[m], vl + H[m] * m, 1}, l, m);
// print(H.size());
}
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R){
ll n = H.size(), q = L.size();
for (ll i=0;i<q;i++)
L[i]++, R[i]++;
H.insert(begin(H), 0);
Ans.resize(q, 0);
for (ll i=n;i>=1;i--){
Mx[i][0] = i;
for (ll j=0;j<19;j++){
if (i + (1<<j) > n or H[Mx[i+(1<<j)][j]] <= H[Mx[i][j]])
Mx[i][j+1] = Mx[i][j];
else
Mx[i][j+1] = Mx[i + (1<<j)][j];
}
}
for (ll i=0;i<q;i++){
ll b = 31 - __builtin_clz(R[i] - L[i] + 1), m = Mx[R[i] - (1<<b) + 1][b];
if (H[Mx[L[i]][b]] >= H[m])
m = Mx[L[i]][b];
quer[m].push_back(i);
}
solve(H, L, R, 1, n);
for (int i=0;i<q;i++)
if (L[i] == R[i])
Ans[i] = H[L[i]];
return Ans;
}
