#include<bits/stdc++.h>
using namespace std;
#include<meetings.h>
#define int long long
const int inf=1e18;
int maxh=20;
struct segtree{
vector<pair<int,int> > tree;
segtree(int n, vector<int32_t>& a){
tree.resize(n*4);
build(0, n, 0, a);
}
pair<int,int> build(int l, int r, int v, vector<int32_t>& a){
if(l+1==r){
return tree[v]={a[l], l};
}
int m=l+(r-l)/2;
return tree[v]=max(build(l, m, v*2+1, a), build(m, r, v*2+2, a));
}
pair<int,int> query(int l, int r, int v, int ql, int qr){
if(qr<=l || r<=ql) return {0, -1};
if(ql<=l && r<=qr) return tree[v];
int m=l+(r-l)/2;
return max(query(l, m, v*2+1, ql, qr), query(m, r, v*2+2, ql, qr));
}
};
int cost(int l, int r, vector<int32_t>& h, segtree& seg, int n){
if(r<l) return 0;
if(l==r) return h[l];
auto x=seg.query(0, n, 0, l, r+1);
int mmax=x.first;
int ind=x.second;
int left=cost(l, ind-1, h, seg, n)+(r-ind+1)*mmax;
int right=cost(ind+1, r, h, seg, n)+(ind-l+1)*mmax;
return min(left, right);
}
vector<int> minimum_costs(vector<int32_t> h, vector<int32_t> l, vector<int32_t> r){
int n=h.size();
int q=r.size();
segtree seg(n, h);
vector<int> ans(q, inf);
for(int i=0; i<q; i++){
ans[i]=cost(l[i], r[i], h, seg, n);
}
return ans;
}
/*signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, q;
cin >> n>> q;
vector<int32_t> h(n);
for(int i=0; i<n; i++){
cin >> h[i];
}
vector<int32_t> l(q);
vector<int32_t> r(q);
for(int i=0; i<q; i++){
cin >> l[i] >> r[i];
}
vector<int> ans=minimum_costs(h, l, r);
for(auto e: ans){
cout << e << "\n";
}
}*/
