#include<bits/stdc++.h>
using namespace std;
#include<meetings.h>
#define int long long
const int inf=1e18;
vector<int> minimum_costs(vector<int32_t> h, vector<int32_t> l, vector<int32_t> r){
int n=h.size(); int q=l.size();
vector<int> cost(q, inf);
vector<int> left(n);
vector<int> right(n);
vector<pair<int,int> > stack;
for(int i=0; i<q; i++){
left.assign(n, 0);
right.assign(n, 0);
stack.clear(); int last=-1;
for(int j=l[i]; j<=r[i]; j++){
//cout << "left " << j << " ";
int cnt=0;
while(!stack.empty() && stack[last].first<h[j]){
cnt+=stack[last].second;
stack.pop_back();
last--;
}
if(!stack.empty()){
left[j]=stack[last].first*stack[last].second;
}
left[j]+=cnt*h[j];
stack.push_back({h[j], cnt+1});
last++;
//cout << j << " " << left[j] << "\n";
}
stack.clear(); last=-1;
for(int j=r[i]; j>=l[i]; j--){
//cout << "right " << j << " ";
int cnt=0;
while(!stack.empty() && stack[last].first<h[j]){
cnt+=stack[last].second;
stack.pop_back();
last--;
}
if(!stack.empty()){
right[j]=stack[last].first*stack[last].second;
}
right[j]+=cnt*h[j];
stack.push_back({h[j], cnt+1});
last++;
//cout << j << " " << right[j] << "\n";
}
int best=inf;
for(int j=l[i]; j<=r[i]; j++){
best=min(best, left[j]+right[j]+h[j]);
}
cost[i]=best;
}
return cost;
}
/*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";
}
}*/
