#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
const int N = 1e5 + 10;
int mxl[N] , mxr[N] , a[N] , n , q;
long long dpl[N] , dpr[N];
long long Solve(int l , int r)
{
for(int i = l ; i <= r ; i++)
{
if(mxl[i] < l)
{
dpl[i] = 1LL * (i - l + 1) * a[i];
continue;
}
dpl[i] = 1LL * (i - mxl[i]) * a[i] + dpl[mxl[i]];
}
for(int i = r ; i >= l ; i--)
{
if(mxr[i] > r)
{
dpr[i] = 1LL * (r - i + 1) * a[i];
continue;
}
dpr[i] = 1LL * (mxr[i] - i) * a[i] + dpr[mxr[i]];
}
long long res = dpl[l] + dpr[l] - a[l];
for(int i = l + 1 ; i <= r ; i++)
res = min(res , dpl[i] + dpr[i] - a[i]);
return res;
}
vector <long long> minimum_costs(vector <int> H , vector <int> L , vector <int> R)
{
n = H.size();
q = L.size();
for(int i = 0 ; i < n ; i++)
a[i] = H[i];
vector <int> st;
for(int i = 0 ; i < n ; i++)
{
mxl[i] = -1;
while(!st.empty())
{
if(a[i] >= a[st.back()])
st.pop_back();
else
{
mxl[i] = st.back();
break;
}
}
st.push_back(i);
}
st.clear();
for(int i = n - 1 ; i >= 0 ; i--)
{
mxr[i] = n + 1;
while(!st.empty())
{
if(a[i] >= a[st.back()])
st.pop_back();
else
{
mxr[i] = st.back();
break;
}
}
st.push_back(i);
}
vector <long long> res(q);
for(int i = 0 ; i < q ; i++)
res[i] = Solve(L[i] , R[i]);
return res;
}
