#include "meetings.h"
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
struct minseg{
pii T[2202020];
int sz = 1 << 20;
void init(vector <int> &H)
{
int i;
for(i=0; i<H.size(); i++){
T[i + sz] = pii(H[i], i);
}
for(i=sz-1; i; i--){
T[i] = max(T[i << 1], T[i << 1 | 1]);
}
}
int getmax(int l, int r)
{
pii ret(-1, -1);
l += sz; r += sz;
for(; l<=r; ){
if(l & 1) ret = max(ret, T[l]);
if(~r & 1) ret = max(ret, T[r]);
l = l + 1 >> 1;
r = r - 1 >> 1;
}
return ret.second;
}
};
struct line{
ll x, a, b;
line() {}
line(ll x, ll a, ll b) : x(x), a(a), b(b) {}
};
struct deq{
line D[808080];
int S[808080], E[808080];
ll V[808080];
int n;
bool t;
void init(bool _t, int _n)
{
int i;
t = _t; n = _n;
for(i=0; i<n; i++){
S[i] = i; E[i] = i;
D[i] = line(i, 0, 0);
}
}
void addval(int p, ll v)
{
if(t) p = n - 1 - p;
V[p] += v;
}
void addline(int p, ll x, ll a, ll b)
{
if(t){
p = n - 1 - p, x = n - 1 - x;
b = (n - 1) * a + b; a = -a;
}
int &s = S[p], &e = E[p];
b -= V[p];
for(; s<=e; e--){
if(D[e].a == a && D[e].b < b) return;
if(D[e].a * D[e].x + D[e].b < a * D[e].x + b){
D[++e] = line((D[e].b - b) / (a - D[e].a) + 1, a, b);
return;
}
}
D[++e] = line(x, a, b);
}
ll getval(int p, ll x)
{
if(t) p = n - 1 - p, x = n - 1 - x;
int k = upper_bound(D + S[p], D + E[p] + 1, x, [&](ll x, line l){
return x < l.x;
}) - D - 1;
return D[k].a * x + D[k].b + V[p];
}
void merge(int p, int q)
{
if(t) p = n - 1 - p, q = n - 1 - q;
int i;
if(E[p] - S[p] < E[q] - S[q]){
swap(S[p], S[q]); swap(E[p], E[q]);
swap(V[p], V[q]);
}
if(S[p] < S[q]){
for(i=S[q]; i<=E[q]; i++){
D[i].b += V[q] - V[p];
D[++E[p]] = D[i];
}
}
else{
for(i=E[q]; i>=S[q]; i--){
D[i].b += V[q] - V[p];
D[--S[p]] = D[i];
}
}
}
};
minseg T;
deq DL, DR;
vector <int> H, L, R;
vector <int> Q[808080];
vector <ll> A;
int n;
int dnc(int s, int e)
{
if(s > e) return -1;
int m, l, r;
ll v, h;
m = T.getmax(s, e); h = H[m];
l = dnc(s, m - 1); r = dnc(m + 1, e);
for(int &q: Q[m]){
if(L[q] == m && R[q] == m) A[q] = h;
else if(L[q] == m) A[q] = DR.getval(r, R[q]) + h;
else if(R[q] == m) A[q] = DL.getval(l, L[q]) + h;
else A[q] = min(DL.getval(l, L[q]) + h * (R[q] - m + 1),
DR.getval(r, R[q]) + h * (m - L[q] + 1));
}
if(l != -1) DL.merge(m, l);
DL.addval(m, h * (e - m + 1));
DL.addline(m, s, -h, (r != -1? DL.getval(r, m + 1) : 0) + h * (m + 1));
if(r != -1) DL.merge(m, r);
if(r != -1) DR.merge(m, r);
DR.addval(m, h * (m - s + 1));
DR.addline(m, e, h, (l != -1? DR.getval(l, m - 1) : 0) - h * (m - 1));
if(l != -1) DR.merge(m, l);
return m;
}
vector <ll> minimum_costs(vector <int> _H, vector <int> _L, vector <int> _R)
{
int i;
swap(H, _H); swap(L, _L); swap(R, _R);
n = H.size(); A.resize(L.size());
T.init(H); DL.init(0, n); DR.init(1, n);
for(i=0; i<L.size(); i++){
Q[T.getmax(L[i], R[i])].push_back(i);
}
dnc(0, n - 1);
return A;
}
