#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;
int sp[MAXK][MAXN];
vector <ll> res;
pll all_queries[MAXN];
vector <pair <pll,ll> > questions[MAXN];
ll a[MAXN];
struct line{
ll a,b,r;
ll eval(ll x,ll lazy){
return a * x + b + lazy;
}
};
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);
}
void dfs(ll l,ll r,deque <line> &s,ll &lazy){
if (l > r)return;
ll mid = max_id(l,r);
// cout<<"DFS "<<l<<' '<<r<<' '<<mid<<endl;
deque <line> L,R;
ll wL=0,wR=0;
dfs(l,mid-1,L,wL);
dfs(mid+1,r,R,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 = L.back().eval(mid-1,wL) + a[mid] - a[mid] * mid;
while (!R.empty()&&intersect(T,R.front(),wR) >= R.front().r){
T.r = R.front().r;
R.pop_front();
}
if (!R.empty()){
T.r = max(T.r,intersect(T,R.front(),wR));
}
// cout<<"DFS "<<l<<' '<<r<<' '<<mid<<endl;
// if (sz(L))cout<<"T "<<T.a<<' '<<T.b<<' '<<L.back().a<<' '<<L.back().b<<' '<<L.back().eval(mid-1)<<' '<<a[mid] - a[mid] * mid<<endl;
if (sz(L) > sz(R)){
swap(s,L);
swap(lazy,wL);
s.push_back({T.a,T.b - lazy,T.r});
for (auto x:R){
x.b += wR-lazy;
s.push_back(x);
}
}
else{
swap(s,R);
swap(lazy,wR);
s.push_front({T.a,T.b - lazy,T.r});
for (ll i = sz(L)-1;i>=0;i--){
line x = L[i];
x.b += wL-lazy;
s.push_front(x);
}
}
// cout<<"DFS "<<l<<' '<<r<<' '<<mid<<endl;
// for (auto x:s){
// 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 + (*lower_bound(s.begin(),s.end(),y,[](line x,ll val){return x.r < val;})).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 <>());
}
deque <line> tmp;
ll tmp2;
dfs(0,n-1,tmp,tmp2);
}
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();
return res;
}
