#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define isz(a) ((signed)a.size())
using ll = long long;
struct query{
int l, r;
};
struct monotonic_stack{
vector <pair <int, int>> st;
ll sum;
monotonic_stack(){
st.clear();
sum = 0;
}
void insert(int x){
int len = 1;
while (not st.empty() and st.back().first <= x){
len += st.back().second;
sum -= (ll)st.back().first * st.back().second;
st.pop_back();
}
st.emplace_back(x, len);
sum += (ll)x * len;
}
};
const int N = 750'000 + 5;
int n, q;
int a[N];
query b[N];
ll ans[N];
ll tans[N];
vector <ll> minimum_costs(vector <int> _a, vector <int> _l, vector <int> _r){
n = isz(_a);
q = isz(_l);
For(i, 0, n){
a[i] = _a[i];
}
For(i, 0, q){
auto l = _l[i], r = _r[i];
b[i] = query{l, r};
}
For(iq, 0, q){
auto &[l, r] = b[iq];
ForE(i, l, r){
tans[i] = -a[i];
}
monotonic_stack st;
ForE(i, l, r){
st.insert(a[i]);
tans[i] += st.sum;
}
st = monotonic_stack();
FordE(i, r, l){
st.insert(a[i]);
tans[i] += st.sum;
}
ans[iq] = *min_element(tans + l, tans + r + 1);
}
return vector <ll>(ans, ans + q);
}
