#include "meetings.h"
#include <iostream>
#include <vector>
#include "meetings.h"
#include <iostream>
using namespace std;
typedef long long ll;
// #define ll ll
#define Line pair<ll,ll>
#define Data pair<ll,ll>
const ll LG=20,inf=2e9,N=1e6+10;
Data sp[N][LG];
ll ans[N],pre[N];
ll a[N],n,q;
vector<vector<ll>> qry[N];
ll get(ll ql,ll qr)
{
qr++;
Data cur={-inf,0};
for(ll j=LG-1;j>=0;j--)
{
if((ql+(1<<j))<=qr)
{
cur=max(cur,sp[ql][j]);
ql+=(1<<j);
}
}
return -cur.second;
}
Line seg[N<<2];
ll lzy[N<<2];
void set(int i,int m,int c,int l=1,int r=n,int v=1)
{
if(i<l or r<i)return;
if(l==r)
{
seg[v]={m,c};
return;
}
if(l==r)
int md=(l+r)>>1,lc=v<<1,rc=lc|1;
set(i,m,c,l,md,lc);
set(i,m,c,md+1,r,rc);
}
void push(int l,int r,int v)
{
int md=(l+r)>>1,lc=v<<1,rc=lc|1;
seg[v].second+=lzy[v];
if(l!=r)
{
lzy[lc]+=lzy[v];
lzy[rc]+=lzy[v];
}
lzy[v]=0;
}
void add(int i,int m,int c,int l=1,int r=n,int v=1)
{
push(l,r,v);
if(m<l or r<i)return;
if(i<=l and r<=m)
{
lzy[v]+=c;
push(l,r,v);
return;
}
int md=(l+r)>>1,lc=v<<1,rc=lc|1;
add(i,m,c,l,md,lc);
add(i,m,c,md+1,r,rc);
}
void upd(int i,int m,int sl,int xt,int l=1,int r=n,int v=1)
{
push(l,r,v);
if(m<l or r<i)return;
if(i<=l and r<=m)
{
ll betx=inter(seg[v],{sl,xt});
return;
}
int md=(l+r)>>1,lc=v<<1,rc=lc|1;
upd(i,m,sl,xt,l,md,lc);
upd(i,m,sl,xt,md+1,r,rc);
}
void solve(ll l,ll r)
{
if(l>r)return;
ll m=get(l,r);
solve(l,m-1);
solve(m+1,r);
for(auto cq:qry[m])
{
ll l=cq[0],r=cq[1],ind=cq[2];
ans[ind]=min(ans[ind],getmin(r)+1ll*(m-l+1)*a[m]);
// ans[ind]=min(ans[ind],pre[r]+1ll*(m-l+1)*a[m]);
}
// pre[m]=;
set(m,0,a[m]+((m>l)?pre[m-1]:0));
add(m+1,r,1ll*(m-l+1)*a[m]);
upd(m+1,r,a[m],pre[m]-1ll*m*a[m]);
}
std::vector<long long> minimum_costs(std::vector<int> h, std::vector<int> l,vector<int> r) {
n=h.size(),q=l.size();
for(ll i=0;i<=q;i++)ans[i]=1e18;
for(ll i=0;i<=n;i++)
{
// pre[i]=0;
set(i,0,0);
if(i)a[i]=h[i-1];
qry[i].clear();
sp[i][0]={h[i-1],-i};
}
for(ll j=1;j<LG;j++)
{
for(ll i=1;i+(1<<j)-1<=n;i++)
sp[i][j]=max(sp[i][j-1],sp[i+(1<<(j-1))][j-1]);
}
for(ll i=0;i<q;i++)
{
l[i]++;
r[i]++;
ll m=get(l[i],r[i]);
qry[m].push_back({l[i],r[i],i});
}
solve(1,n);
for(ll i=0;i<=n;i++)
{
if(i)a[i]=h[n-i];
qry[i].clear();
sp[i][0]={a[i],-i};
set(i,0,0);
}
for(ll j=1;j<LG;j++)
{
for(ll i=1;i+(1<<j)-1<=n;i++)
sp[i][j]=max(sp[i][j-1],sp[i+(1<<(j-1))][j-1]);
}
for(ll i=0;i<q;i++)
{
swap(l[i],r[i]);
l[i]=n-l[i]+1;
r[i]=n-r[i]+1;
ll m=get(l[i],r[i]);
qry[m].push_back({l[i],r[i],i});
}
solve(1,n);
vector<long long> fnl;
for(ll i=0;i<q;i++)
{
fnl.push_back(ans[i]);
}
return fnl;
}
