#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//#define int ll
using pii = pair<int,int>;
#define sz(x) ((int)(x).size())
const int nmax = 75e4 + 5;
const int nbit = 20;
const ll inf = 4e18 + 5;
namespace RMQ {
vector<signed> costs;
int rmq[nbit][nmax];
int lg2[nmax];
void init(vector<signed> H) {
costs = move(H);
int n = sz(costs);
for(int i = 2; i <= n; i++)
lg2[i] = lg2[i >> 1] + 1;
for(int i = 0; i < n; i++)
rmq[0][i] = i;
for(int step = 1; step < nbit; step++)
for(int i = 0; i + (1 << step) <= n; i++)
rmq[step][i] = (costs[rmq[step - 1][i]] <= costs[rmq[step - 1][i + (1 << step - 1)]]? rmq[step - 1][i + (1 << step - 1)] : rmq[step - 1][i]);
}
int query(int l, int r) {
int step = lg2[r - l + 1];
return costs[rmq[step][l]] <= costs[rmq[step][r - (1 << step) + 1]]? rmq[step][r - (1 << step) + 1] : rmq[step][l];
}
};
pii qs[nmax];
ll rez[nmax];
struct line {
ll m, b;
line(ll x = 0, ll y = inf): m(x), b(y) {;}
ll operator()(const ll& x) const {
return m * x + b;
}
line operator + (const line& x) const { return line(x.m + m, min(inf, x.b + b)); }
line operator += (const line& x) { return *this = *this + x; }
};
int N;
struct LiChao {
line aint[nmax * 4];
line lazy[nmax * 4];
void pushlazy(int node) {
aint[2 * node] += lazy[node];
aint[2 * node + 1] += lazy[node];
lazy[2 * node + 1] += lazy[node];
lazy[2 * node] += lazy[node];
lazy[node] = line(0, 0);
}
void forcepush(line x, int node, int cl, int cr) {
int mid = cl + cr >> 1;
if(x(mid) < aint[node](mid)) {
swap(x, aint[node]);
}
if(cl == cr) return;
pushlazy(node);
if(x(cl) < aint[node](cl))
forcepush(x, 2 * node, cl, mid);
else
forcepush(x, 2 * node + 1, mid + 1, cr);
return;
}
void pushline(int node, int cl, int cr) {
int mid = cl + cr >> 1;
forcepush(aint[node], 2 * node, cl, mid);
forcepush(aint[node], 2 * node + 1, mid + 1, cr);
aint[node] = line();
}
void maxline(int l, int r, line x, int node, int cl, int cr) {
if(r < cl || cr < l) return;
if(l <= cl && cr <= r) { forcepush(x, node, cl, cr); return; }
pushlazy(node);
int mid = cl + cr >> 1;
maxline(l, r, x, 2 * node, cl, mid);
maxline(l, r, x, 2 * node + 1, mid + 1, cr);
}
void addline(int l, int r, line x, int node, int cl, int cr) {
if(r < cl || cr < l) return;
if(l <= cl && cr <= r) {
aint[node] += x;
lazy[node] += x;
return;
}
pushlazy(node);
pushline(node, cl, cr);
int mid = cl + cr >> 1;
addline(l, r, x, 2 * node, cl, mid);
addline(l, r, x, 2 * node + 1, mid + 1, cr);
}
ll query(int p, int node, int cl, int cr) {
if(cr < p || p < cl) return inf;
if(cl == cr) {return aint[node](p); }
int mid = cl + cr >> 1;
pushlazy(node);
return min({aint[node](p), query(p, 2 * node, cl, mid), query(p, 2 * node + 1, mid + 1, cr)});
}
ll query(int p) { return query(p, 1, 0, N - 1); }
void addline(int l, int r, line x) { addline(l, r, x, 1, 0, N - 1); }
void maxline(int l, int r, line x) { maxline(l, r, x, 1, 0, N - 1); }
};
namespace CartTree {
int Ls[nmax], Rs[nmax];
int L[nmax], R[nmax];
ll val[nmax];
vector<int> atrqs[nmax];
int root;
LiChao toleft, toright;
void init(vector<signed> H) {
vector<int> st;
for(int i = 0; i < sz(H); i++) {
val[i] = H[i];
int last = -1;
while(!st.empty() && H[st.back()] <= H[i])
R[st.back()] = i - 1,
last = st.back(),
st.pop_back();
L[i] = (st.empty()? 0 : st.back() + 1);
Ls[i] = last;
Rs[i] = -1;
if(!st.empty())
Rs[st.back()] = i;
else
root = i;
st.emplace_back(i);
}
for(auto x : st)
R[x] = sz(H) - 1;
}
void push(int idx, int l, int r) {
int mid = RMQ::query(l, r);
atrqs[mid].emplace_back(idx);
}
void start(int node) {
if(node == -1)
return;
start(Ls[node]);
start(Rs[node]);
for(auto idx : atrqs[node]) {
auto [l, r] = qs[idx];
ll lv = (l == node? 0 : toright.query(l));
ll rv = (r == node? 0 : toleft.query(r));
lv += val[node] * (r - node + 1);
rv += val[node] * (node - l + 1);
rez[idx] = min({lv, rv, (r - l + 1) * val[node]});
}
auto [l, r] = pii{L[node], R[node]};
toleft.addline(node, r, line{0, (node - l + 1) * val[node]});
toleft.maxline(node, r, line(val[node], (l == node? 0 : toleft.query(node - 1)) + -(node - 1) * val[node]));
toright.addline(l, node, line{0, (r - node + 1) * val[node]});
toright.maxline(l, node, line(-val[node], (r == node? 0 : toright.query(node + 1)) + (node + 1) * val[node]));
return;
}
}
std::vector<long long> minimum_costs(std::vector<signed> H, std::vector<signed> L, std::vector<signed> R) {
N = sz(H);
CartTree::init(H);
RMQ::init(H);
for(int i = 0; i < sz(L); i++) {
qs[i] = pii{L[i], R[i]};
CartTree::push(i, L[i], R[i]);
}
CartTree::start(CartTree::root);
vector<ll> r;
r.reserve(sz(L));
for(int i = 0; i < sz(L); i++)
r.emplace_back(rez[i]);
return r;
}
//#undef int
