#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
template<class A> using v=vector<A>;
typedef v<int> vi;
typedef long long ll;
#define sz(S) (int)(S).size()
#define pb push_back
#define rsz resize
#define f first
#define s second
#define mp make_pair
#define get4(a,b,c,d,...) d
#define lp3(x,a,b) for(int x=(a);x<(b);x++)
#define lp2(x,a) lp3(x,0,a)
#define lp1(a) lp2(loopvar,a)
#define lp(x...) get4(x,lp3,lp2,lp1,0)(x)
#define trv(x,S) for(auto& x:(S))
template<class A,class B> bool ckmax(A& a1,const B& b1) {return a1<b1?a1=b1,1:0;}
template<class A,class B> bool ckmin(A& a1,const B& b1) {return a1>b1?a1=b1,1:0;}
const int mx=1000000;
int q;
v<ll> ans;
ll pcost1[mx];
ll pcost2[mx];
void getcost(const v<ll>& H,int l,int r,ll rst[])
{
v<pair<ll,int>> stps;
ll ccost=0;
lp(i,l,r+1)
{
stps.pb(mp(H[i],1)); ccost+=H[i];
while(sz(stps)>1&&stps[sz(stps)-1].f>=stps[sz(stps)-2].f)
{
ccost+=(stps[sz(stps)-1].f-stps[sz(stps)-2].f)*stps[sz(stps)-2].s;
stps[sz(stps)-2].f=stps[sz(stps)-1].f;
stps[sz(stps)-2].s+=stps[sz(stps)-1].s;
stps.pop_back();
}
rst[i]=ccost;
}
}
v<ll> minimum_costs(vi H, vi L,vi R)
{
q=sz(L);
v<ll> hl(sz(H)),hlr(sz(H));
vi Lr(q),Rr(q);
lp(i,sz(H)) hl[i]=H[i];
lp(i,sz(H)) hlr[i]=H[sz(H)-1-i];
lp(i,q) Lr[i]=sz(H)-1-L[i];
lp(i,q) Rr[i]=sz(H)-1-R[i];
lp(i,q) swap(Lr[i],Rr[i]);
ans.rsz(q);
trv(x,ans) x=1ll<<60;
lp(qn,q)
{
getcost(hl,L[qn],R[qn],pcost1);
getcost(hlr,Lr[qn],Rr[qn],pcost2);
lp(i,L[qn],R[qn]+1) ckmin(ans[qn],pcost1[i]+pcost2[sz(H)-1-i]-H[i]);
}
return ans;
}
