#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define MP make_pair
#define pll pair <ll,ll>
#define fi first
#define se second
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1LL)
#define MASK(i) (1LL << (i))
ll n,q;
const ll MAXN = 7.5e5+100;
const ll MAXK = 20;
const ll INF = 1e18;
ll sp[MAXK][MAXN];
vector <ll> res;
pll all_queries[MAXN];
vector <pair <pll,ll> > questions[MAXN];
ll a[MAXN];
struct line{
mutable ll a,b;
ll r;
ll eval(ll x,ll lazy)const {
return a * x + b + lazy;
}
bool operator < (const line &p)const{
return r < p.r;
}bool operator < (const ll &p)const{
return r < p;
}
};
ll max_id(ll l,ll r){
ll sz = __lg(r-l+1);
ll L = sp[sz][l],R = sp[sz][r-MASK(sz)+1];
if (a[R] > a[L])return R;
else return L;
}
ll intersect(line i,line j,ll lazy){
j.b+=lazy;
if (j.a==i.a)return i.b>j.b?-INF:INF;
return (i.b-j.b)/(j.a-i.a);
}
set <line,less<>> s;
void dfs(ll l,ll r,set<line>::iterator &is,set <line>::iterator &ie,ll &lazy){
if (l > r){is = s.end(),ie = s.end(),lazy = 0;return;}
if (l==r){
is = ie = s.insert({0,a[l],l}).fi;
lazy = 0;
}
else{
ll mid = max_id(l,r);
set<line>::iterator Lb,Lf,Rb,Rf;
ll wL=0,wR=0;
if (mid == l){
dfs(mid+1,r,Rf,Rb,wR);
wR += (mid-l+1)*a[mid];
lazy = wR;
is = s.insert({0,a[mid]-lazy,mid}).fi;
ie = Rb;
}
else if (mid==r){
dfs(l,mid-1,Lf,Lb,wL);
lazy = wL;
is = Lf;
ie = s.insert({0,(*Lb).eval(mid-1,wL)+ a[mid]-lazy,mid}).fi;
}
else{
// cout<<"DFS "<<l<<' '<<r<<' '<<mid<<endl;
dfs(l,mid-1,Lf,Lb,wL);
dfs(mid+1,r,Rf,Rb,wR);
wR += (mid-l+1)*a[mid];
line T;
T.a = a[mid];
T.b = a[mid] * (-l+1);
T.r = mid;
if (mid != l)T.b = (*Lb).eval(mid-1,wL) + a[mid] - a[mid] * mid;
while (Rf!=s.end()&&intersect(T,*Rf,wR) >= (*Rf).r){
T.r = (*Rf).r;
Rf = s.erase(Rf);
}
if (Rf != s.end()){
T.r = max(T.r,intersect(T,*Rf,wR));
}
// cout<<"TTT "<<l<<' '<<r<<' '<<mid<<endl;
// if (mid>l)cout<<"T "<<T.a<<' '<<T.b<<' '<<(*Lb).eval(mid-1,wL) + a[mid] - a[mid] * mid<<endl;
if (mid-l+1>r-mid){
lazy = wL;
auto itmid = s.insert({T.a,T.b - lazy,T.r}).fi;
is = (mid > l ? Lf : itmid);
for (auto it = Rf;it != s.end();it ++){
(*it).b += wR-lazy;
}
}
else{
lazy = wR;
auto itmid = s.insert({T.a,T.b - lazy,T.r}).fi;
is = (mid > l ? Lf : itmid);
for (auto it = Lf;it != itmid;it ++){
(*it).b += wL-lazy;
}
}
ie = prev(s.end());
}
// cout<<"DFS "<<l<<' '<<r<<' '<<mid<<endl;
// for (auto it = is;it != s.end();it++){
// line x = *it;
// cout<<x.a<<' '<<x.b+lazy<<' '<<x.r<<endl;
// }
}
while (!questions[l].empty() && questions[l].back().fi.fi <= r){
ll id = questions[l].back().fi.se;
ll pre = questions[l].back().se;
ll y = questions[l].back().fi.fi;
res[id] = min(res[id],pre + ((*s.lower_bound(y)).eval(y,lazy)));
questions[l].pop_back();
}
}
void solve(){
for (ll i = 0;i < n;i ++)sp[0][i] = i;
for (ll j = 1;j < MAXK;j ++){
for (ll i = 0;i + MASK(j) - 1 < n;i ++){
if (a[sp[j-1][i+MASK(j-1)]] > a[sp[j-1][i]])sp[j][i] = sp[j-1][i+MASK(j-1)];
else sp[j][i] = sp[j-1][i];
}
}
for (ll i = 0;i < n;i ++)questions[i].clear();
for (ll i = 0;i < q;i ++){
ll l = all_queries[i].fi,r = all_queries[i].se;
ll mid = max_id(l,r);
if (mid < r)questions[mid+1].push_back(MP(MP(r,i),a[mid] * (mid-l+1)));
res[i] = min(res[i],a[mid]*(r-l+1));
}
for (ll i = 0;i < n;i ++){
sort(questions[i].begin(),questions[i].end(),greater <>());
}
set<line>::iterator it1,it2;
ll tmp2;
dfs(0,n-1,it1,it2,tmp2);
s.clear();
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R){
n = sz(H);
q = sz(L);
res=vector <ll> (q,INF);
for (ll i = 0;i < n;i ++)a[i] = H[i];
for (ll i = 0;i < q;i ++){
all_queries[i] = MP(L[i],R[i]);
}
solve();
reverse(a,a+n);
for (ll i = 0;i < q;i ++){
all_queries[i] = MP(n-1-R[i],n-1-L[i]);
}
solve();
// cout<<sizeof(set<line>::iterator)<<endl;
return res;
}
