#include "meetings.h"
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif
#define ar array
typedef long long ll;
typedef int32_t ii;
vector<ll> minimum_costs(vector<int> a, vector<int> l, vector<int> r) {
int n = a.size(), q = l.size();
if(n <= 5000 && q <= 5000){
vector<ll> res(q);
auto get = [&](vector<int> a){
int n = a.size();
ll cur = 0;
vector<int> ss;
vector<ll> cost(n);
for(int i=0;i<n;i++){
while(!ss.empty() && a[ss.back()] <= a[i]){
int id = ss.back();
ss.pop_back();
if(ss.empty()) cur -= a[id] * 1ll * (id + 1);
else cur -= a[id] * 1ll * (id - ss.back());
}
if(ss.empty()) cur += a[i] * 1ll * (i + 1);
else cur += a[i] * 1ll * (i - ss.back());
ss.push_back(i);
cost[i] += cur;
}
ss.clear(); cur = 0;
for(int i= n - 1;~i;i--){
while(!ss.empty() && a[ss.back()] <= a[i]){
int id = ss.back();
ss.pop_back();
if(ss.empty()) cur -= a[id] * 1ll * (n - id);
else cur -= a[id] * 1ll * (ss.back() - id);
}
if(ss.empty()) cur += a[i] * 1ll * (n - i);
else cur += a[i] * 1ll * (ss.back() - i);
ss.push_back(i);
cost[i] += cur;
}
ll mn = 1e18;
for(int i=0;i<n;i++){
mn = min(mn, cost[i] - a[i]);
}
return mn;
};
for(int i=0;i<q;i++){
vector<int> b;
for(int j=l[i];j<=r[i];j++){
b.push_back(a[j]);
}
res[i] = get(b);
}
return res;
}
assert(false);
vector<ll> res(q);
return res;
}
