#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
typedef long long ll;
const int N = 100005;
int n, qq;
vector<ll> solv2(vector<int> H, vector<int> L, vector<int> R)
{
vector<ll> v;
for (int ii = 0; ii < qq; ++ii)
{
int l = L[ii];
int r = R[ii];
vector<ll> ans(n);
for (int i = l; i <= r; ++i)
ans[i] = 0;
stack<pair<int, int> > s;
ll yans = 0;
for (int i = l; i <= r; ++i)
{
int q = 1;
while (!s.empty() && H[i] >= s.top().fi)
{
yans -= s.top().fi * 1LL * s.top().se;
q += s.top().se;
s.pop();
}
s.push(m_p(H[i], q));
yans += s.top().fi * 1LL * s.top().se;
ans[i] += yans;
}
while (!s.empty())
s.pop();
yans = 0;
for (int i = r; i >= l; --i)
{
int q = 1;
while (!s.empty() && H[i] >= s.top().fi)
{
yans -= s.top().fi * 1LL * s.top().se;
q += s.top().se;
s.pop();
}
s.push(m_p(H[i], q));
yans += s.top().fi * 1LL * s.top().se;
ans[i] += yans - H[i];
}
yans = ans[l];
for (int i = l; i <= r; ++i)
yans = min(yans, ans[i]);
v.push_back(yans);
}
return v;
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R)
{
n = sz(H);
qq = sz(L);
return solv2(H, L, R);
}
