#include "meetings.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
#include <stack>
typedef long long llong;
const int MAXN = 100000 + 10;
const int INF = 1e9;
int n, q;
int a[MAXN];
llong prefix[MAXN];
llong suffix[MAXN];
std::stack <std::pair <int, llong>> st;
std::vector <llong> ans;
llong solveFor(int l, int r)
{
if (l == r)
{
return a[l];
}
while (!st.empty()) st.pop();
for (int i = l ; i <= r ; ++i)
{
while (!st.empty() && a[st.top().first] < a[i])
{
st.pop();
}
if (st.empty())
{
st.push({i, 1LL * (i - l + 1) * a[i]});
} else
{
st.push({i, st.top().second + 1LL * (i - st.top().first + 1) * a[i]});
}
prefix[i] = st.top().second;
}
while (!st.empty()) st.pop();
for (int i = r ; i >= l ; --i)
{
while (!st.empty() && a[st.top().first] < a[i])
{
st.pop();
}
if (st.empty())
{
st.push({i, 1LL * (r - i + 1) * a[i]});
} else
{
st.push({i, st.top().second + 1LL * (st.top().first - i + 1) * a[i]});
}
suffix[i] = st.top().second;
}
llong ans = suffix[l];
for (int i = l + 1 ; i <= r ; ++i)
{
ans = std::min(ans, prefix[i - 1] + suffix[i]);
}
return ans;
}
std::vector <llong> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R)
{
n = H.size();
for (int i = 0 ; i < n ; ++i)
{
a[i] = H[i];
}
q = L.size();
ans.resize(q);
for (int i = 0 ; i < q ; ++i)
{
ans[i] = solveFor(L[i], R[i]);
}
return ans;
}
