#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 1000 * 1000 + 7;
ll tab[N], l[N];
pair<pair<int, int>, int> que[N];
ll answer[N];
ll Ans(int a, int b)
{
ll ans = I;
vector<pair<ll, int>> kol;
kol.pb(make_pair(I, a - 1));
ll s = 0LL;
l[a - 1] = 0LL;
for(int i = a; i <= b; ++i)
{
while(kol.back().st <= tab[i])
{
int r = (int)kol.size() - 1;
s -= (ll)(kol[r].nd - kol[r - 1].nd) * kol[r].st;
kol.pop_back();
}
s += (ll)(i - kol.back().nd) * tab[i];
kol.pb(make_pair(tab[i], i));
l[i] = s;
}
kol.clear();
kol.pb(make_pair(I, b + 1));
s = 0LL;
for(int i = b; i >= a; --i)
{
while(kol.back().st <= tab[i])
{
int r = (int)kol.size() - 1;
s -= (ll)(kol[r - 1].nd - kol[r].nd) * kol[r].st;
kol.pop_back();
}
s += (ll)(kol.back().nd - i) * tab[i];
ans = min(l[i] - tab[i] + s, ans);
kol.pb(make_pair(tab[i], i));
}
return ans;
}
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R)
{
vector<ll> ans;
int n = H.size(), q = L.size();
for(int i = 1; i <= n; ++i) tab[i] = H[i - 1];
for(int i = 1; i <= q; ++i)
que[i] = make_pair(make_pair(L[i - 1] + 1, R[i - 1] + 1), i);
for(int i = 1; i <= q; ++i)
ans.pb(Ans(que[i].st.st, que[i].st.nd));
return ans;
}
