#include "meetings.h"
#include <algorithm>
#include <iostream>
#include <cassert>
#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) * 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) * a[i]});
}
suffix[i] = st.top().second;
}
prefix[l - 1] = 0;
suffix[r + 1] = 0;
int opt = l;
llong ans = suffix[l];
for (int i = l + 1 ; i <= r ; ++i)
{
if (ans > prefix[i - 1] + suffix[i])
{
ans = prefix[i - 1] + suffix[i];
opt = i;
}
}
for (int i = l ; i < opt ; ++i)
{
assert(prefix[i - 1] + suffix[i] >= prefix[i] + suffix[i + 1]);
}
for (int i = opt ; i <= r ; ++i)
{
assert(prefix[i - 1] + suffix[i] <= prefix[i] + suffix[i + 1]);
}
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;
}
