#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<ll>
#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")
ll n,q;
ll 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(ll l,ll r) {
ll bit=31-__builtin_clz(r-l+1);
return max(a[l][bit], a[r-(1<<bit)+1][bit]);
}
void apply(ll v, ll tl, ll 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(ll v,ll tl,ll 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(ll v,ll tl,ll tr,ll l,ll 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);
ll 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(ll v,ll tl,ll tr,ll idx) {
if (tl==tr)return t[v].F;
push(v,tl,tr);
ll tm=(tl+tr)/2;
if (idx<=tm)return get(v*2,tl,tm,idx);
return get(v*2+1,tm+1,tr,idx);
}
ll solve(ll l,ll r,bool prnt) {
if (l>r)return -1;
ll mid=abs(getmax(l,r).S);
ll lc=solve(l,mid-1,prnt);
ll rc=solve(mid+1,r,prnt);
up(1,0,n-1,mid,mid,{1,-mid},1);
for (ll x:Q[mid]) {
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);
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(vector <int> H, vector <int> L, vector <int> R) {
n=H.size();
q=L.size();
for (ll i=0;i<n;i++)
a[i][0]={H[i],i};
for (ll bit=1;bit<20;bit++)
for (ll i=0;i<n-(1<<(bit-1));i++)
a[i][bit]=max(a[i][bit-1],a[i+(1<<(bit-1))][bit-1]);
for (ll 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,0);
reverse(Q.begin(),Q.begin()+n);
t.assign(MAXN+1,{0,0});
lazy.assign(MAXN+1,{0,0});
a.assign(MAXN+1,vp(20));
reverse(H.begin(),H.end());
for (ll i=0;i<n;i++)
a[i][0]={H[i],-i};
for (ll bit=1;bit<20;bit++)
for (ll i=0;i<n-(1<<(bit-1));i++)
a[i][bit]=max(a[i][bit-1],a[i+(1<<(bit-1))][bit-1]);
for (ll i=0;i<q;i++) {
ql[i]=n-1-R[i];
qr[i]=n-1-L[i];
}
solve(0,n-1,1);
vector <ll> res;
for (ll i=0;i<q;i++)res.pb(ans[i]);
return res;
}
// signed main(){
// ll n,q;
// cin>>n>>q;
// vector <int> H,L,R;
// while(n--) {
// ll x;
// cin>>x;
// H.pb(x);
// }
// while (q--) {
// ll l,r;
// cin>>l>>r;
// L.pb(l);
// R.pb(r);
// }
// vector <ll> wtf=minimum_costs(H,L,R);
// for (ll x:wtf)cout<<x<<" ";
// }
