#include "meetings.h"
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
using namespace std;
ll n;vector<ll >ans;
const ll N=5090;
ll tree[N*4],pa[N],lef[N];
vector<ll>vv,h,w;
vector<ll>v;ll c=0;
void up(int ind,int st,int end,int uind,int x)
{
tree[uind]=x;
}
ll get (int ind,int st,int end,int l,int r)
{
return tree[l];
}
ll solve(int l,int r)
{
v.clear();
ll mn=1e17;
ll re=0;
for(ll i=l;i<r+1;i++)
{
ll r=0;
int x=v.size();x--;
while(x>=0&&v[x]<=h[i])
{
ll cnt=get(0,0,c-1,v[x],v[x]);
up(0,0,c-1,v[x],0);
re-=cnt*pa[v[x]];
r+=cnt;x--;
v.pop_back();
}
r++;
v.pb(h[i]);
re+=r*pa[h[i]];
lef[i]=re;
up(0,0,c-1,h[i],r);
}
v.clear();
memset(tree,0,sizeof tree);
re=0;
for(ll i=r;i>l-1;i--)
{
ll r=0;
int x=v.size();x--;
while(x>=0&&v[x]<=h[i])
{
ll cnt=get(0,0,c-1,v[x],v[x]);
up(0,0,c-1,v[x],0);
re-=cnt*pa[v[x]];
r+=cnt;
x--;
v.pop_back();
}
r++;
v.pb(h[i]);
re+=r*pa[h[i]];
mn=min(mn,lef[i]+re-pa[h[i]]);
up(0,0,c-1,h[i],r);
}
memset(tree,0,sizeof tree);
memset(lef,0,sizeof lef);
return mn;
}
vector<long long> minimum_costs(vector<int> H, vector<int> L,vector<int> R) {
ans.clear();
vv.clear();
n=H.size();
for(ll i=0;i<n;i++){
w.pb(H[i]);
}
sort(w.begin(),w.end());
w.pb(-1);
for(ll i=1;i<w.size();i++)
{
if(w[i]!=w[i-1])vv.pb(w[i-1]);
}
for(ll i=0;i<n;i++)
{
ll x=lower_bound(vv.begin(),vv.end(),H[i])-vv.begin();
h.pb(x);
pa[x]=H[i];
}
c=vv.size();
ll q=L.size();
for(ll j=0;j<q;j++)
{
ans.pb(solve(L[j],R[j]));
}
return ans;
}
/*
4 2
2 4 3 5
0 2
1 3
*/
