#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 75e4;
const ll INF = 1e18;
struct Data
{
int l, r, p;
};
int N, Q;
ll A[MAXN+10];
Data B[MAXN+10];
ll ans[MAXN+10];
ll val[MAXN+10];
vector<ll> minimum_costs(vector<int> _H, vector<int> _L, vector<int> _R)
{
N=_H.size(); Q=_L.size();
for(int i=1; i<=N; i++) A[i]=_H[i-1];
for(int i=1; i<=Q; i++) B[i]={_L[i-1]+1, _R[i-1]+1, i};
for(int i=1; i<=Q; i++)
{
for(int j=B[i].l; j<=B[i].r; j++) val[j]=-A[j];
ll t=0;
vector<int> S;
S.push_back(B[i].l-1);
for(int j=B[i].l; j<=B[i].r; j++)
{
while(S.size()>1 && A[S.back()]<=A[j])
{
t-=A[S[S.size()-1]]*(S[S.size()-1]-S[S.size()-2]);
S.pop_back();
}
t+=A[j]*(j-S.back());
S.push_back(j);
val[j]+=t;
}
t=0;
S.clear();
S.push_back(B[i].r+1);
for(int j=B[i].r; j>=B[i].l; j--)
{
while(S.size()>1 && A[S.back()]<=A[j])
{
t-=A[S[S.size()-1]]*(S[S.size()-2]-S[S.size()-1]);
S.pop_back();
}
t+=A[j]*(S.back()-j);
S.push_back(j);
val[j]+=t;
}
ans[i]=INF;
//for(int j=B[i].l; j<=B[i].r; j++) printf("%lld ", val[j]); printf("\n");
for(int j=B[i].l; j<=B[i].r; j++) ans[i]=min(ans[i], val[j]);
}
vector<ll> ret;
for(int i=1; i<=Q; i++) ret.push_back(ans[i]);
return ret;
}
