#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define tol(bi) (1LL<<((ll)(bi)))
#include "meetings.h"
#define INF LONG_LONG_MAX
struct SegTree{
vector<ll> segtree;
vector<ll> lazy;
SegTree(int n){
segtree.resize(tol(ceil(log2(n)+1))-1,0);
lazy.resize(segtree.size(), 0ll);
}
void dallan(int node){
segtree[node]+=lazy[node];
if (node*2+1<segtree.size()){
lazy[node*2+1]+=lazy[node];
lazy[node*2+2]+=lazy[node];
}
lazy[node]=0;
}
void update(int tarl, int tarr, ll val, int l = 0, int r = -1, int node = 0){
if (r==-1) r = segtree.size()/2;
dallan(node);
if (l>=tarl && r<=tarr){
lazy[node]+=val;
dallan(node);
return;
}
if (l>tarr || r<tarl) return;
int mid = l+(r-l)/2;
update(tarl, tarr, val, l, mid, node*2+1);
update(tarl, tarr, val, mid+1, r, node*2+2);
segtree[node]=min(segtree[node*2+1],segtree[node*2+2]);
}
ll query(int tarl, int tarr, int l = 0, int r = -1, int node = 0){
if (r==-1) r = segtree.size()/2;
dallan(node);
if (l>=tarl && r<=tarr) return segtree[node];
if (l>tarr || r<tarl) return INF;
int mid = l+(r-l)/2;
ll lnode = query(tarl, tarr, l, mid, node*2+1);
ll rnode = query(tarl, tarr, mid+1, r, node*2+2);
return min(lnode,rnode);
}
};
vector<long long> minimum_costs(vector<int> arr, vector<int> L, vector<int> R) {
ll q = L.size();
ll n = arr.size();
vector<ll> ansarr(q,0);
SegTree segtree(n);
vector<ll> leftdp(n);
vector<ll> rightdp(n);
vector<ll> sonra(n,n);
vector<ll> once(n,-1);
vector<ll> stak;
for (ll i = 0; i < n; i++){
while (stak.size() && arr[stak.back()]<=arr[i]){
stak.pop_back();
};
if (stak.size()==0){
leftdp[i]=(i+1)*arr[i];
}
else {
once[i]=stak.back();
leftdp[i]=leftdp[stak.back()]+arr[i]*(i-stak.back());
}
stak.push_back(i);
}
stak.clear();
for (ll i = n-1; i >= 0; i--){
while (stak.size() && arr[stak.back()]<=arr[i]){
stak.pop_back();
}
if (stak.size()==0){
rightdp[i]=(n-1-i+1)*arr[i];
}
else {
sonra[i]=stak.back();
rightdp[i]=rightdp[stak.back()]+arr[i]*(stak.back()-i);
}
stak.push_back(i);
}
for (ll i = 0; i < n; i++){
segtree.update(i,i,leftdp[i]+rightdp[i]-arr[i]);
}
cout<<endl;
vector<array<int,3>> quarr(q);
for (int i = 0; i < q; ++i)
{
quarr[i]={L[i],R[i],i};
}
int BLOK = sqrt(n);
sort(quarr.begin(), quarr.end(), [&](array<int,3> a, array<int,3> b){
if (a[0]/BLOK==b[0]/BLOK) return a[1]<b[1];
return a[0]<b[0];
});
int lastl = 0;
int lastr = n-1;
for (int i = 0; i < quarr.size(); i++){
int l = quarr[i][0];
int r = quarr[i][1];
while (lastl>l){
int node = lastl-1;
while (node<n){
segtree.update(node,sonra[node]-1,arr[node]);
node=sonra[node];
}
lastl--;
}
while (lastr<r){
int node = lastr+1;
while (node>=0){
segtree.update(once[node]+1,node,arr[node]);
node=once[node];
}
lastr++;
}
while (lastl<l){
int node = lastl;
while (node<n){
segtree.update(node,sonra[node]-1,-arr[node]);
node=sonra[node];
}
lastl++;
}
while (lastr>r){
int node = lastr;
while (node>=0){
segtree.update(once[node]+1,node,-arr[node]);
node=once[node];
}
lastr--;
}
ansarr[quarr[i][2]]=segtree.query(l,r);
}
return ansarr;
}
