#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define sz(x) (int)x.size()
#define ALL(x) begin(x), end(x)
#define loop(n, i) for (int i = 0; i < n; i++)
#define rev(n, i) for (int i = n - 1; i >= 0; i--)
typedef signed i32;
typedef long long i64;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<i32> vi32;
typedef vector<vi32> vvi32;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
vector<int> s;
int rmax(int i, int l, int r, int ql, int qr)
{
if (qr < l || r < ql)
return 0;
if (ql <= l && r <= qr)
return s[i];
int m = (l + r) / 2;
return max(rmax(2 * i, l, m, ql, qr), rmax(2 * i + 1, m + 1, r, ql, qr));
}
vi minimum_costs(vi32 H, vi32 L, vi32 R)
{
int Q = sz(L);
vi C(Q);
int N = sz(H);
int treeN = 1;
while (treeN < N)
treeN *= 2;
s.assign(2 * treeN, {});
loop(N, i)
{
s[i + treeN] = H[i];
}
rev(treeN, i)
{
s[i] = max(s[2 * i], s[2 * i + 1]);
}
for (int j = 0; j < Q; ++j)
{
int l = L[j];
int r = R[j];
int best = 1e18;
for (int x = l; x <= r; x++)
{
int cur = 0;
int mxCur = 0;
for (int i = x; i <= r; i++)
{
mxCur = max(mxCur, (i64)H[i]);
cur += mxCur;
}
mxCur = 0;
for (int i = x; i >= l; i--)
{
mxCur = max(mxCur, (i64)H[i]);
cur += mxCur;
}
best = min(best, cur);
}
C[j] = best;
}
return C;
}
