#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
struct lichao
{
int A, l, r;
long long B, lazy;
lichao() : A(0), l(0), r(0), B(0x3fffffffffffffffLL), lazy(0) {}
};
const int SZ=1<<20;
pair<int,int> Mtree[2*SZ];
lichao ltree[2*SZ], rtree[2*SZ];
vector<long long> res;
vector<tuple<int,int,int>> Q[750001];
pair<int,int> get_max(int s, int e)
{
pair<int,int> ret(-1,-1);
for(s+=SZ,e+=SZ;s<=e;s>>=1,e>>=1) {
if(s&1) ret=max(ret,Mtree[s++]);
if(~e&1) ret=max(ret,Mtree[e--]);
}
return ret;
}
void lazy_propagation(lichao *tree, int bit, int s, int e)
{
if(tree[bit].lazy) {
tree[bit].B+=tree[bit].lazy;
if(s<e) {
tree[2*bit].lazy+=tree[bit].lazy;
tree[2*bit+1].lazy+=tree[bit].lazy;
}
tree[bit].lazy=0;
}
}
int get_sign(long long a)
{
return a<0 ? -1:a>0;
}
void add_line(lichao *tree, int n1, int n2, int A, long long B, int bit=1, int s=0, int e=SZ-1)
{
int m=(s+e)>>1;
lazy_propagation(tree,bit,s,e);
if(n2<n1 || n2<s || e<n1) return;
if(n1<=s && e<=n2) {
int &pA=tree[bit].A;
long long &pB=tree[bit].B, ys=1LL*A*s+B, ym=1LL*A*m+B, ye=1LL*A*e+B, pys=1LL*pA*s+pB, pym=1LL*pA*m+pB, pye=1LL*pA*e+pB;
if(ym<pym) {
swap(pA,A); swap(pB,B);
swap(pys,ys); swap(pym,ym); swap(pye,ye);
}
if(pys<=ys && pye<=ye) return;
if(get_sign(ys-pys)*get_sign(ym-pym)<0 || ym==pym && ys<pys) add_line(tree,n1,n2,A,B,2*bit,s,m);
else add_line(tree,n1,n2,A,B,2*bit+1,m+1,e);
return;
}
add_line(tree,n1,n2,A,B,2*bit,s,m);
add_line(tree,n1,n2,A,B,2*bit+1,m+1,e);
}
void add_tree(lichao *tree, int n1, int n2, long long v, int bit=1, int s=0, int e=SZ-1)
{
int m=(s+e)>>1;
lazy_propagation(tree,bit,s,e);
if(n2<n1 || n2<s || e<n1) return;
if(n1<=s && e<=n2) {
tree[bit].lazy=v;
lazy_propagation(tree,bit,s,e);
return;
}
add_tree(tree,n1,n2,v,2*bit,s,m);
add_tree(tree,n1,n2,v,2*bit+1,m+1,e);
}
long long get_y(lichao *tree, int x, int bit=1, int s=0, int e=SZ-1)
{
int m=(s+e)>>1;
lazy_propagation(tree,bit,s,e);
if(s==e) return 1LL*tree[bit].A*x+tree[bit].B;
return min(x<=m ? get_y(tree,x,2*bit,s,m):get_y(tree,x,2*bit+1,m+1,e),1LL*tree[bit].A*x+tree[bit].B);
}
void solve(int s, int e)
{
if(s>e) return;
auto[M,m]=get_max(s,e);
solve(s,m-1);
solve(m+1,e);
for(auto[l,r,i]: Q[m]) res[i]=min(get_y(ltree,l)+(r-m+1LL)*M,get_y(rtree,r)+(m-l+1LL)*M);
add_tree(ltree,s,m-1,(e-m+1LL)*M);
add_line(ltree,s,m,-M,(m<e ? get_y(ltree,m+1):0)+M*(m+1LL));
add_tree(rtree,m+1,e,(m-s+1LL)*M);
add_line(rtree,m,e,M,(s<m ? get_y(rtree,m-1):0)+M*(1LL-m));
}
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R)
{
int N=H.size(), M=L.size();
res.resize(M);
for(int i=0;i<N;i++) Mtree[SZ+i+1]={H[i],i+1};
for(int i=SZ;--i;) Mtree[i]=max(Mtree[2*i],Mtree[2*i+1]);
for(int i=0;i<M;i++) {
if(++L[i]<++R[i]) Q[get_max(L[i],R[i]).second].emplace_back(L[i],R[i],i);
else res[i]=H[L[i]-1];
}
solve(1,N);
return res;
}
