#include<bits/stdc++.h>
using namespace std;
#include<meetings.h>
const long long inf=1e18;
struct sparsetable{
int l=20;
vector<vector<pair<int,int> > > table;
sparsetable(int n, vector<int32_t>& a){
table.assign(n, vector<pair<int,int> > (l, make_pair(0, -1)));
for(int i=0; i<n; i++){
table[i][0]={a[i], i};
}
for(int i=1; i<l; i++){
for(int j=0; j+(1<<(i-1))<n; j++){
table[j][i]=max(table[j][i-1], table[j+(1<<(i-1))][i-1]);
}
}
}
pair<int,int> query(int left, int right){
int x=right-left;
pair<int,int> ans={0, -1};
for(int i=0; i<l; i++){
if((x>>i)%2==1){
ans=max(ans, table[left][i]);
left+=(1<<i);
}
}
return ans;
}
};
long long cost(int l, int r, vector<int32_t>& h, sparsetable& sp, int n){
if(r<l) return 0;
if(l==r) return h[l];
auto x=sp.query(l, r+1);
int mmax=x.first;
int ind=x.second;
long long left=cost(l, ind-1, h, sp, n)+(r-ind+1)*(long long)mmax;
long long right=cost(ind+1, r, h, sp, n)+(ind-l+1)*(long long)mmax;
return min(left, right);
}
vector<long long> minimum_costs(vector<int32_t> h, vector<int32_t> l, vector<int32_t> r){
int n=h.size();
int q=r.size();
sparsetable sp(n, h);
vector<long long> ans(q, inf);
for(int i=0; i<q; i++){
ans[i]=cost(l[i], r[i], h, sp, 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";
}
}*/
