#include "meetings.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;
const int tree_siz = 2048*1024-1;
struct segtree
{
ll R_val[tree_siz+1];
ll add[tree_siz+1];
bool is_set[tree_siz+1];
pll set_f[tree_siz+1];
bool is_suf = 0;
segtree(bool suf) : is_suf(suf)
{
rep(i,tree_siz+1)
{
R_val[i] = 1e18;
add[i] = 0;
is_set[i] = 0;
set_f[i] = {0,0};
}
}
void spych(int v, int l, int r)
{
if(is_set[v])
{
is_set[v*2] = 1;
is_set[v*2+1] = 1;
set_f[v*2] = set_f[v];
set_f[v*2+1] = set_f[v];
R_val[v*2] = set_f[v].ff*((l+r)/2)+set_f[v].ss;
R_val[v*2+1] = set_f[v].ff*r+set_f[v].ss;
}
else
{
add[v*2] += add[v];
add[v*2+1] += add[v];
R_val[v*2] += add[v];
R_val[v*2+1] += add[v];
set_f[v*2].ss += add[v];
set_f[v*2+1].ss += add[v];
}
is_set[v] = 0;
set_f[v] = {0,0};
add[v] = 0;
}
void add_seg2(int akt, int p1, int p2, int s1, int s2, ll x)
{
if(p2 < s1 || p1 > s2) return;
if(p1 >= s1 && p2 <= s2)
{
add[akt] += x;
set_f[akt].ss += x;
R_val[akt] += x;
return;
}
spych(akt,p1,p2);
add_seg2(akt*2,p1,(p1+p2)/2,s1,s2,x);
add_seg2(akt*2+1,(p1+p2)/2+1,p2,s1,s2,x);
R_val[akt] = R_val[akt*2+1];
}
void set_func2(int akt, int p1, int p2, int s1, int s2, pll f)
{
if(p2 < s1 || p1 > s2) return;
if(p1 >= s1 && p2 <= s2)
{
set_f[akt] = f;
is_set[akt] = 1;
R_val[akt] = f.ff*p2+f.ss;
return;
}
spych(akt,p1,p2);
set_func2(akt*2,p1,(p1+p2)/2,s1,s2,f);
set_func2(akt*2+1,(p1+p2)/2+1,p2,s1,s2,f);
R_val[akt] = R_val[akt*2+1];
}
int rek(int akt, int p1, int p2, pll f)
{
if(p1 == p2) return p1;
spych(akt,p1,p2);
if(R_val[akt*2] <= f.ff*((p1+p2)/2)+f.ss) return rek(akt*2,p1,(p1+p2)/2,f);
return rek(akt*2+1,(p1+p2)/2+1,p2,f);
}
int get_first_bad2(int akt, int p1, int p2, int s1, int s2, pll f)
{
if(p2 < s1 || p1 > s2) return 1e9;
if(p1 >= s1 && p2 <= s2)
{
if(R_val[akt] <= f.ff*p2+f.ss) return rek(akt,p1,p2,f);
return 1e9;
}
spych(akt,p1,p2);
int w1 = get_first_bad2(akt*2,p1,(p1+p2)/2,s1,s2,f);
if(w1 != 1e9) return w1;
return get_first_bad2(akt*2+1,(p1+p2)/2+1,p2,s1,s2,f);
}
int get_first_bad(int l, int r, pll f)
{
if(is_suf)
{
l = tree_siz/2-l;
r = tree_siz/2-r;
swap(l,r);
f.ss = f.ss+f.ff*(tree_siz/2);
f.ff *= -1;
}
int ans = get_first_bad2(1,0,tree_siz/2,l,r,f);
if(ans == 1e9) return ans;
if(is_suf) return tree_siz/2-ans;
return ans;
}
void add_seg(int l, int r, ll x)
{
if(is_suf)
{
l = tree_siz/2-l;
r = tree_siz/2-r;
swap(l,r);
}
add_seg2(1,0,tree_siz/2,l,r,x);
}
void set_func(int l, int r, pll f)
{
if(is_suf)
{
l = tree_siz/2-l;
r = tree_siz/2-r;
swap(l,r);
f.ss = f.ss+f.ff*(tree_siz/2);
f.ff *= -1;
}
set_func2(1,0,tree_siz/2,l,r,f);
}
ll get_val(int p)
{
if(is_suf) p = tree_siz/2-p;
int v = 1;
int p1 = 0;
int p2 = tree_siz/2;
while(p1 != p2)
{
spych(v,p1,p2);
if(p <= (p1+p2)/2)
{
v = v*2;
p2 = (p1+p2)/2;
}
else
{
v = v*2+1;
p1 = (p1+p2)/2+1;
}
}
return R_val[v];
}
};
segtree pref_tree(0);
segtree suf_tree(1);
ll H[750001];
pii max_[750001][20];
int n;
vl query_ans;
vector<pair<pii,int>> queries[750001];
int get_max(int l, int r)
{
int lg = __lg(r-l+1);
return max(max_[l][lg],max_[r-(1<<lg)+1][lg]).ss;
}
void solve(int l, int r)
{
if(l > r) return;
int mx = get_max(l,r);
solve(l,mx-1);
solve(mx+1,r);
forall(it,queries[mx])
{
int l2 = it.ff.ff;
int r2 = it.ff.ss;
ll val1 = 1e18;
ll val2 = 1e18;
if(mx != l2) val1 = suf_tree.get_val(l2)+H[mx]*(r2-mx+1);
if(mx != r2) val2 = pref_tree.get_val(r2)+H[mx]*(mx-l2+1);
query_ans[it.ss] = min({val1,val2,H[mx]*(r2-l2+1)});
}
pref_tree.set_func(mx,mx,{0,0});
suf_tree.set_func(mx,mx,{0,0});
pref_tree.add_seg(mx,r,H[mx]*(mx-l+1));
suf_tree.add_seg(l,mx,H[mx]*(r-mx+1));
if(mx != l)
{
ll val = pref_tree.get_val(mx-1);
pll f = {H[mx],val+(1-mx)*H[mx]};
int p = pref_tree.get_first_bad(mx,r,f);
if(p == 1e9) p = r+1;
p--;
if(p >= mx) pref_tree.set_func(mx,p,f);
}
if(mx != r)
{
ll val = suf_tree.get_val(mx+1);
pll f = {-H[mx],val+(1+mx)*H[mx]};
int p = suf_tree.get_first_bad(l,mx,f);
if(p == 1e9) p = l-1;
p++;
if(p <= mx) suf_tree.set_func(p,mx,f);
}
}
vl minimum_costs(vi H2, vi L, vi R)
{
n = siz(H2);
rep(i,n) H[i] = H2[i];
rep(i,n) max_[i][0] = {H[i],i};
rep2(bit,1,19) rep(i,n) max_[i][bit] = max(max_[i][bit-1],(i+(1<<(bit-1)) < n ? max_[i+(1<<(bit-1))][bit-1] : (pii){0,0}));
query_ans.resize(siz(L));
rep(i,siz(L)) queries[get_max(L[i],R[i])].pb({{L[i],R[i]},i});
solve(0,n-1);
return query_ans;
}
