#include "meetings.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <stack>
typedef long long llong;
const int MAXN = 750000 + 10;
const llong INF = 4e18;
const int INTINF = 2e9;
int n, q;
int a[MAXN];
struct Query
{
int l, r;
int idx;
};
Query query[MAXN];
llong answer[MAXN];
llong prefMAX[MAXN];
llong suffMAX[MAXN];
void solve()
{
for (int idx = 1 ; idx <= q ; ++idx)
{
int l = query[idx].l;
int r = query[idx].r;
std::stack <std::array <int, 3>> st;
prefMAX[l - 1] = suffMAX[r + 1] = 0;
st.push({l - 1, 0, INTINF});
for (int i = l ; i <= r ; ++i)
{
prefMAX[i] = prefMAX[i - 1];
while (st.size() && st.top()[2] < a[i])
{
prefMAX[i] -= 1LL * st.top()[1] * st.top()[2];
st.pop();
}
prefMAX[i] += 1LL * (i - st.top()[0]) * a[i];
st.push({i, (i - st.top()[0]), a[i]});
}
while (st.size()) st.pop();
st.push({r + 1, 0, INTINF});
for (int i = r ; i >= l ; --i)
{
suffMAX[i] = suffMAX[i + 1];
while (st.size() && st.top()[2] < a[i])
{
suffMAX[i] -= 1LL * st.top()[1] * st.top()[2];
st.pop();
}
suffMAX[i] += 1LL * (st.top()[0] - i) * a[i];
st.push({i, (st.top()[0] - i), a[i]});
}
answer[idx] = INF;
for (int i = l ; i <= r ; ++i)
{
answer[idx] = std::min(answer[idx], prefMAX[i] + suffMAX[i] - a[i]);
}
}
}
std::vector <llong> minimum_costs(std::vector <int> H, std::vector <int> L, std::vector <int> R)
{
n = H.size();
q = L.size();
for (int i = 1 ; i <= n ; ++i)
{
a[i] = H[i - 1];
}
for (int i = 1 ; i <= q ; ++i)
{
query[i].l = L[i - 1] + 1;
query[i].r = R[i - 1] + 1;
}
solve();
std::vector <llong> sol;
for (int i = 1 ; i <= q ; ++i)
{
sol.push_back(answer[i]);
}
return sol;
}
