#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ii pair<int,int>
const int nax=2e5+5;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,std::vector<int> R){
int Q = L.size();
int N = H.size();
std::vector<long long> C(Q);
vector<long long> left(N);
vector<long long> right(N);
for (int j = 0; j < Q; ++j){
C[j]=1e18;
stack<int> st;
left[L[j]]=H[L[j]];
st.push(L[j]);
for (int i = L[j]+1; i <= R[j]; ++i)
{
while(!st.empty()&&H[i]>=H[st.top()]) st.pop();
if(st.size()) left[i]=left[st.top()]+1ll*(i-st.top())*H[i];
else left[i]=1ll*(i-L[j]+1)*H[i];
st.push(i);
}
/*for (int i = L[j]; i <= R[j]; ++i)
{
cout <<left[i]<<" ";
}cout <<endl;*/
while(!st.empty()) st.pop();
right[R[j]]=H[R[j]];
st.push(R[j]);
for (int i = R[j]-1; i >= L[j]; --i)
{
while(!st.empty()&&H[i]>=H[st.top()]) st.pop();
if(st.size()) right[i]=right[st.top()]+1ll*(st.top()-i)*H[i];
else right[i]=1ll*(R[j]-i+1)*H[i];
st.push(i);
}
/*for (int i = L[j]; i <= R[j]; ++i)
{
cout <<right[i]<<" ";
}cout <<endl;*/
C[j]=min(left[R[j]],right[L[j]]);
for (int i = L[j]+1; i <= R[j]; ++i)
{
C[j]=min(C[j],left[i-1]+right[i]);
}
}
return C;
}
