#include "meetings.h"
#include <iostream>
using namespace std;
typedef long long ll;
#define Data pair<int,int>
const int LG=20,inf=2e9,N=1e5+10;
Data sp[N][LG];
ll ans[N],pre[N];
int a[N];
vector<vector<int>> qry[N];
int get(int ql,int qr)
{
qr++;
Data cur={-inf,0};
for(int j=LG-1;j>=0;j--)
{
if((ql+(1<<j))<=qr)
{
cur=max(cur,sp[ql][j]);
ql+=(1<<j);
}
}
return cur.second;
}
void solve(int l,int r)
{
if(l>r)return;
int m=get(l,r);
solve(l,m-1);
solve(m+1,r);
pre[m]=0;
for(auto cq:qry[m])
{
int l=cq[0],r=cq[1],ind=cq[2];
ans[ind]=min(ans[ind],pre[r]+(m-l+1)*a[m]);
}
pre[m]=a[m]+pre[m-1];
for(int i=m+1;i<=r;i++)pre[i]=min(pre[m]+(i-m)*a[m],pre[i]+(m-l+1)*a[m]);
}
std::vector<long long> minimum_costs(std::vector<int> h, std::vector<int> l,vector<int> r) {
int n=h.size(),q=l.size();
for(int i=0;i<=q;i++)ans[i]=1e18;
for(int i=1;i<=n;i++)
{
pre[i]=0;
a[i]=h[i-1];
qry[i].clear();
sp[i][0]={h[i-1],i};
}
for(int j=1;j<LG;j++)
{
for(int i=1;i+(1<<j)-1<=n;i++)
sp[i][j]=max(sp[i][j-1],sp[i+(1<<(j-1))][j-1]);
}
for(int i=0;i<q;i++)
{
l[i]++;
r[i]++;
int m=get(l[i],r[i]);
qry[m].push_back({l[i],r[i],i});
}
solve(1,n);
for(int i=1;i<=n;i++)
{
a[i]=h[n-i];
qry[i].clear();
sp[i][0]={a[i],i};
pre[i]=0;
}
for(int j=1;j<LG;j++)
{
for(int i=1;i+(1<<j)-1<=n;i++)
sp[i][j]=max(sp[i][j-1],sp[i+(1<<(j-1))][j-1]);
}
for(int i=0;i<q;i++)
{
swap(l[i],r[i]);
l[i]=n-l[i]+1;
r[i]=n-r[i]+1;
int m=get(l[i],r[i]);
qry[m].push_back({l[i],r[i],i});
}
solve(1,n);
vector<long long> fnl;
for(int i=0;i<q;i++)
{
fnl.push_back(ans[i]);
}
return fnl;
}
