#include "meetings.h"
using namespace std;
typedef long long ll;
std::vector<long long> minimum_costs(std::vector<int> h, std::vector<int> l,
std::vector<int> r) {
int n=h.size(),q=l.size(),mx=2;
for(int i=0;i<n;i++)
{
mx=max(mx,h[i]);
}
// if(mx==2)
// {
// // find max elemtn between two occurences between
// }
vector<ll> fnl(q);
vector<ll> cst(n+2,0);
for(int i=0;i<q;i++)
{
int ql=l[i],qr=r[i];
vector<int> c;
ll ans=0;
for(int x=ql;x<=qr;x++)
{
while(c.size()>0 and h[c.back()]<=h[x])
{
int z=c.back();
c.pop_back();
ans-=1ll*(z-((c.size()>0)?(c.back()):(ql-1)))*h[z];
}
int z=x;
ans+=1ll*(z-((c.size()>0)?(c.back()):(ql-1)))*h[z];
c.push_back(x);
cst[x]=ans;
}
ans=0;
ll mi=1e18;
c.clear();
for(int x=qr;x>=ql;x--)
{
while(c.size()>0 and h[c.back()]<=h[x])
{
int z=c.back();
c.pop_back();
ans-=1ll*(((c.size()>0)?(c.back()):(qr+1))-z)*h[z];
}
int z=x;
ans+=1ll*(((c.size()>0)?(c.back()):(qr+1))-z)*h[z];
c.push_back(x);
mi=min(mi,cst[x]+ans-h[x]);
}
fnl[i]=mi;
}
return fnl;
}
