#include <bits/stdc++.h>
#include "meetings.h"
#define ll long long
#define pb push_back
#define S second
#define F first
#define pii pair<ll,ll>
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define vp vector<pii>
#define vvp vector<vp>
#define vb vector<bool>
#define vvb vector<vb>
#define INF 1000000000000000
#define MOD 1000000007
#define MAXN 750000
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
int n,q;
int ql[MAXN+1],qr[MAXN+1];
vector<ll> ans(MAXN+1,INF);
vvp a(MAXN+1,vp(20));
vvi Q(MAXN+1);
vp t(4*MAXN+1);
vp lazy(4*MAXN+1);
pii getmax(int l,int r) {
int bit=31-__builtin_clz(r-l+1);
return max(a[l][bit], a[r-(1<<bit)+1][bit]);
}
void apply(int v, int tl, int tr, pii x) {
if(x.F) {
t[v] = { tl * x.F , tr * x.F};
lazy[v] ={ x.F , 0};
}
t[v].F += x.S;
t[v].S += x.S;
lazy[v].S += x.S;
}
void push(int v,int tl,int tr) {
apply(v*2,tl,(tl+tr)/2,lazy[v]);
apply(v*2+1,(tl+tr)/2+1,tr,lazy[v]);
lazy[v]={0,0};
}
void up(int v,int tl,int tr,int l,int r,pii x,bool all) {
if (l>r)return;
if (tl==l && tr==r) {
if (all || tr*x.F+x.S < t[v].S) {
apply(v,tl,tr,x);
return;
}
if (tl*x.F + x.S >= t[v].F)
return;
}
push(v,tl,tr);
int tm=(tl+tr)/2;
up(v*2,tl,tm,l,min(r,tm),x,all);
up(v*2+1,tm+1,tr,max(l,tm+1),r,x,all);
t[v]={t[2*v].F,t[2*v+1].S};
}
ll get(int v,int tl,int tr,int idx) {
if (tl==tr)return t[v].F;
push(v,tl,tr);
int tm=(tl+tr)/2;
if (idx<=tm)return get(v*2,tl,tm,idx);
return get(v*2+1,tm+1,tr,idx);
}
int solve(int l,int r) {
if (l>r)return -1;
int mid=getmax(l,r).S;
int lc=solve(l,mid-1);
int rc=solve(mid+1,r);
up(1,0,n-1,mid,mid,{1,-mid},1);
for (int x:Q[mid]) {
// cout<<x<<" "<<mid<<" "<<get(1,0,n-1,qr[x])<<'\n';
ans[x]=min(get(1,0,n-1,qr[x])+(mid-ql[x]+1ll)*a[mid][0].F,ans[x]);
}
up(1,0,n-1,mid,r,{0,(mid-l+1ll)*a[mid][0].F},1);
// cout<<((~lc?get(1,0,n-1,mid-1):0) - (mid-1ll)*a[mid][0].F)<<"\n";
up(1,0,n-1,mid,r,{a[mid][0].F, (~lc?get(1,0,n-1,mid-1):0) - (mid-1ll)*a[mid][0].F },0);
return mid;
}
vector <ll> minimum_costs(vi H, vi L, vi R) {
n=H.size();
q=L.size();
for (int i=0;i<n;i++)
a[i][0]={H[i],i};
for (int bit=1;bit<20;bit++)
for (int i=0;i<n-(1<<(bit-1));i++)
a[i][bit]=max(a[i][bit-1],a[i+(1<<(bit-1))][bit-1]);
for (int i=0;i<q;i++) {
ql[i]=L[i];
qr[i]=R[i];
Q[getmax(ql[i],qr[i]).S].pb(i);
}
solve(0,n-1);
Q.assign(MAXN+1,{});
reverse(H.begin(),H.end());
for (int i=0;i<n;i++)
a[i][0]={H[i],i};
for (int bit=1;bit<20;bit++)
for (int i=0;i<n-(1<<(bit-1));i++)
a[i][bit]=max(a[i][bit-1],a[i+(1<<(bit-1))][bit-1]);
for (int i=0;i<q;i++) {
ql[i]=n-1-R[i];
qr[i]=n-1-L[i];
Q[getmax(ql[i],qr[i]).S].pb(i);
}
solve(0,n-1);
vector <ll> res;
for (int i=0;i<q;i++)res.pb(ans[i]);
return res;
}
/*signed main(){
vector <ll> awdq=minimum_costs({2,4,3,5},{0,1},{2,3});
for (int x:awdq)cout<<x<<" ";
}*/
