#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
const int N = 75e4 + 10 , Lg = 20;
const long long inf = 1e17;
int n , q , nexR[N] , nexL[N];
long long ansR[N] , ansL[N];
vector <int> a , L , R;
struct item{
long long ans , sum;
int l , r;
};
item valL[N][Lg] , valR[N][Lg];
item MergeL(item al , item ar)
{
item res;
res.l = al.l;
res.r = ar.r;
if(res.l == -1 || res.r == -1)
{
res.sum = res.ans = inf;
return res;
}
res.sum = al.sum + ar.sum;
res.ans = min(al.ans + 1LL * (ar.r - ar.l) * a[ar.l] , ar.ans + al.sum);
return res;
}
item MergeR(item al , item ar)
{
item res;
res.l = al.l;
res.r = ar.r;
if(res.l == -1 || res.r == -1)
{
res.sum = res.ans = inf;
return res;
}
res.sum = al.sum + ar.sum;
res.ans = min(al.ans + ar.sum , ar.ans + 1LL * (al.r - al.l) * a[al.r]);
return res;
}
vector <long long> minimum_costs(vector <int> H , vector <int> LL , vector <int> RR)
{
vector <long long> res;
a = H;
L = LL;
R = RR;
n = H.size();
q = L.size();
vector <int> st;
for(int i = 0 ; i < n ; i++)
{
nexL[i] = -1;
nexR[i] = -1;
while(!st.empty())
{
if(a[st.back()] < a[i])
{
nexR[st.back()] = i;
st.pop_back();
}
else
{
nexL[i] = st.back();
break;
}
}
st.push_back(i);
}
for(int i = 0 ; i < n ; i++)
{
ansL[i] = inf;
if(nexL[i] == -1)
continue;
if(nexL[i] == i - 1)
{
ansL[i] = a[i] + a[i - 1];
continue;
}
vector <int> pos;
int las = i - 1;
while(las != nexL[i])
{
pos.push_back(las);
las = nexL[las];
}
long long tmp = 0;
while(!pos.empty())
{
int now = pos.back(); pos.pop_back();
ansL[i] = min(ansL[i] , tmp + ansL[now] + a[i] + 1LL * (i - now - 1) * a[now]);
tmp += a[las];
tmp += 1LL * (now - las - 1) * a[now];
las = now;
}
}
for(int i = n - 1 ; i >= 0 ; i--)
{
ansR[i] = inf;
if(nexR[i] == -1)
continue;
if(nexR[i] == i + 1)
{
ansR[i] = a[i] + a[i + 1];
continue;
}
vector <int> pos;
int las = i + 1;
while(las != nexR[i])
{
pos.push_back(las);
las = nexR[las];
}
long long tmp = 0;
while(!pos.empty())
{
int now = pos.back(); pos.pop_back();
ansR[i] = min(ansR[i] , tmp + ansR[now] + a[i] + 1LL * (now - i - 1) * a[now]);
tmp += a[las];
tmp += 1LL * (las - now - 1) * a[now];
las = now;
}
}
for(int i = 0 ; i < n ; i++)
{
valL[i][0].ans = ansL[i]; valL[i][0].l = nexL[i]; valL[i][0].r = i;
if(nexL[i] == -1)
valL[i][0].sum = inf;
else
valL[i][0].sum = a[nexL[i]] + 1LL * (i - nexL[i] - 1) * a[i];
valR[i][0].ans = ansR[i]; valR[i][0].r = nexR[i]; valR[i][0].l = i;
if(nexR[i] == -1)
valR[i][0].sum = inf;
else
valR[i][0].sum = a[nexR[i]] + 1LL * (nexR[i] - i - 1) * a[i];
}
for(int j = 1 ; j < Lg ; j++) for(int i = 0 ; i < n ; i++)
{
if(valL[i][j - 1].l == -1)
valL[i][j] = valL[i][j - 1];
else
valL[i][j] = MergeL(valL[valL[i][j - 1].l][j - 1] , valL[i][j - 1]);
if(valR[i][j - 1].r == -1)
valR[i][j] = valR[i][j - 1];
else
valR[i][j] = MergeR(valR[i][j - 1] , valR[valR[i][j- 1].r][j - 1]);
}
for(int asd = 0 ; asd < q ; asd++)
{
long long ans = inf;
if(L[asd] == R[asd])
{
ans = a[L[asd]];
res.push_back(ans);
continue;
}
bool flg = false;
int pos = L[asd];
item now;
for(int i = Lg - 1 ; i >= 0 ; i--) if(valR[pos][i].r <= R[asd] && valR[pos][i].r != -1)
{
if(!flg)
now = valR[pos][i];
else
now = MergeR(now , valR[pos][i]);
flg = true;
pos = now.r;
}
if(flg)
ans = min(ans , now.ans + 1LL * (R[asd] - now.r) * a[now.r]);
flg = false;
pos = R[asd];
for(int i = Lg - 1 ; i >= 0 ; i--) if(valL[pos][i].l >= L[asd] && valL[pos][i].l != -1)
{
if(!flg)
now = valL[pos][i];
else
now = MergeL(valL[pos][i] , now);
flg = true;
pos = now.l;
}
if(flg)
ans = min(ans , now.ans + 1LL * (now.l - L[asd]) * a[now.l]);
res.push_back(ans);
}
return res;
}
