#include "meetings.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct sliding_minimum{
int l, val;
deque<pair<int,int> > deq;
sliding_minimum(int _l, vector<signed> v){
l = _l;
val = 0;
for(int i = 0; i<l; i++){
add(v[i]);
}
}
void add(int a){
int i = 1;
while(!deq.empty()&&deq.back().first<=a){
i+=deq.back().second;
val-= deq.back().first * deq.back().second;
deq.pop_back();
}
val+=a*i;
deq.push_back({a, i});
}
void remove(){
val -= deq.front().first;
if(deq.front().second==1){
deq.pop_front();
}
else{
deq.front().second--;
}
}
void slide(int a){
add(a);
remove();
}
};
int N, Q;
vector<int> minimum_costs(vector<signed> H, vector<signed> L, vector<signed> R) {
N = H.size();
Q = L.size();
vector<vector<int> > prec1(N, vector<int> (N, -1));
for(int i = 1; i<=N; i++){
sliding_minimum sm(i, H);
for(int j = 0; i+j-1<N;j++){
prec1[j][j+i-1] = sm.val;
//cout<<"i: "<<j<<" j: "<<j+i-1<<" : "<<sm.val<<endl;
if(i+j<N) sm.slide(H[j+i]);
}
}
reverse(H.begin(), H.end());
vector<vector<int> > prec2(N, vector<int> (N, -1));
for(int i = 1; i<=N; i++){
sliding_minimum sm(i, H);
for(int j = 0; i+j-1<N;j++){
prec2[N-1-(j+i-1)][N-1-j] = sm.val;
if(i+j<N) sm.slide(H[j+i]);
}
}
reverse(H.begin(), H.end());
vector<int> C(Q);
for(int i = 0; i<Q; i++){
int ans = 2e18;
for(int j = L[i]; j<=R[i]; j++){
ans = min(ans, prec1[L[i]][j] + prec2[j][R[i]] - (int)H[j]);
}
C[i] = ans;
}
return C;
}
