#ifdef NYAOWO
#include "grader.cpp"
#endif
#include "meetings.h"
#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
using namespace std;
using LL = long long;
using pii = pair<LL, LL>;
const int MAXN = 5010;
const LL INF = 1e10;
int N, Q;
LL h[MAXN];
LL cl[MAXN], cr[MAXN];
LL query(int l, int r) {
LL tot = 0;
vector<pii> v; // {index, value}
v.eb(l - 1, INF);
For(i, l, r) {
while(v.back().S < h[i]) {
auto p = v.back(); v.pop_back();
tot -= p.S * (p.F - v.back().F);
}
tot += h[i] * (i - v.back().F);
cl[i] = tot;
v.eb(i, h[i]);
}
tot = 0;
v.clear();
v.eb(r + 1, INF);
Forr(i, r, l) {
while(v.back().S < h[i]) {
auto p = v.back(); v.pop_back();
tot -= p.S * (v.back().F - p.F);
}
tot += h[i] * (v.back().F - i);
cr[i] = tot;
v.eb(i, h[i]);
}
LL ans = cl[l] + cr[l] - h[l];
For(i, l + 1, r) ans = min(ans, cl[i] + cr[i] - h[i]);
return ans;
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R) {
N = sz(H);
Q = sz(L);
if(N <= 5000) {
For(i, 0, N - 1) h[i] = H[i];
vector<LL> C(Q);
For(i, 0, Q - 1) {
C[i] = query(L[i], R[i]);
}
return C;
}
std::vector<long long> C(Q);
for (int j = 0; j < Q; ++j) {
C[j] = H[L[j]];
}
return C;
}
