#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
int N;
int Q;
int lst[750100];
int l, r;
pair<int,int> st[3100100];
void build(int i, int s, int e){
if(s == e){
st[i] = {lst[s],s};
return;
}
int m = (s + e)/2;
build(i * 2,s,m);
build(i * 2 + 1, m + 1, e);
st[i] = max(st[i * 2],st[i * 2 + 1]);
}
pair<int,int> query(int i, int s, int e, int S, int E){
if(S <= s && e <= E){
return st[i];
}
int m = (s + e)/2;
if(S <= m && m < E){
return max(query(i*2,s,m,S,E), query(i*2+1,m+1,e,S,E));
}
if(S <= m) return query(i * 2, s, m ,S, E);
if(m < E) return query(i * 2 + 1, m + 1, e, S, E);
}
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
N = H.size();
Q = L.size();
for(int i = 0; i < N; i++){
lst[i] = H[i];
}
build(1,0,N-1);
vector<long long int> banna;
for(int i = 0; i < Q; i++){
l = L[i];
r = R[i];
queue<vector<long long int>> pq;
pq.push({0,l,r});
long long int ans = 1e18;
while(!pq.empty()){
vector<long long int> v = pq.front();
pq.pop();
if(v[1] == v[2]){
ans = min(ans, v[0] + lst[v[1]]);
continue;
}
int it = query(1,0,N-1,v[1],v[2]).second;
if(it != v[1]){
pq.push({lst[it] * (v[2] - it + 1) + v[0], v[1], it - 1 });
}
if(it != v[2]){
pq.push({lst[it] * (it - v[1] + 1) + v[0], it + 1, v[2] });
}
}
banna.push_back(ans);
}
return banna;
}
