#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 7.5e5 + 10;
int n, q;
ll h[maxn];
ll calc(int pivot, int left, int right)
{
ll mx = 0, ans = 0;
for (int i = pivot; i >= left; i --)
{
mx = max(mx, h[i]);
ans += mx;
}
mx = h[pivot];
for (int i = pivot + 1; i <= right; i ++)
{
mx = max(mx, h[i]);
ans += mx;
}
return ans;
}
ll pref[maxn], suff[maxn];
ll query(int left, int right)
{
ll ans = 1e18;
/**for (int pivot = left; pivot <= right; pivot ++)
{
ll cur = calc(pivot, left, right);
cout << cur << " ";
ans = min(ans, calc(pivot, left, right));
}
cout << endl;*/
stack < int > st;
ll sum = 0;
for (int i = left; i <= right; i ++)
{
while(!st.empty() && h[st.top()] < h[i])
{
int val = st.top();
st.pop();
int bef = left - 1;
if (!st.empty())
bef = st.top();
sum = sum - (ll)(val - bef) * h[val];
}
int bef = left - 1;
if (!st.empty())
{
bef = st.top();
}
sum = sum + (ll)(i - bef) * h[i];
st.push(i);
pref[i] = sum;
///cout << pref[i] << " ";
}
///cout << endl;
while(!st.empty())
st.pop();
sum = 0;
for (int i = right; i >= left; i --)
{
while(!st.empty() && h[st.top()] < h[i])
{
int val = st.top();
st.pop();
int aft = right + 1;
if (!st.empty())
aft = st.top();
sum = sum - (ll)(aft - val) * h[val];
}
int aft = right + 1;
if (!st.empty())
{
aft = st.top();
}
sum = sum + (ll)(aft - i) * h[i];
st.push(i);
suff[i] = sum;
}
for (int i = left; i <= right; i ++)
{
ans = min(ans, pref[i] + suff[i] - h[i]);
}
return ans;
}
vector<long long> minimum_costs(vector<int> H, vector<int> L,
vector<int> R)
{
n = H.size();
q = L.size();
for (int i = 0; i < n; i ++)
{
h[i] = H[i];
}
vector < ll > res(q);
for (int i = 0; i < q; i ++)
{
res[i] = query(L[i], R[i]);
}
return res;
}
