#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint INF = 1e18;
struct LiChaoSegmentTree {
struct Line {
lint m, c; //y = mx + c
Line(): m(0), c(0) { }
Line(lint M, lint C): m(M), c(C) { }
inline lint get(lint x) {
return (m * x) + c;
}
};
lint n;
vector<Line> tree;
vector<lint> lazy;
lint get_size(int tl, int tr) {
if (tl == tr) {
return 1;
}
int mid = (tl + tr) / 2;
return 1 + get_size(tl, mid) + get_size(mid + 1, tr);
}
void build(int n, int tl, int tr) {
if (tl == tr) {
tree[n] = Line();
lazy[n] = 0;
return;
}
int mid = (tl + tr) / 2;
build(n * 2, tl, mid);
build(n * 2 + 1, mid + 1, tr);
tree[n] = Line(0, INF);
lazy[n] = 0;
}
void build(int n) {
this->n = n;
lint sz = get_size(1, n) + 1;
tree.resize(sz + 1);
lazy.resize(sz + 1);
build(1, 1, n);
}
inline void push(int n) {
if (lazy[n]) {
tree[n * 2].c += lazy[n];
tree[n * 2 + 1].c += lazy[n];
lazy[n * 2] += lazy[n];
lazy[n * 2 + 1] += lazy[n];
lazy[n] = 0;
}
}
void add(int n, int tl, int tr, int le, int ri, lint val) {
if (tl > tr || tr < le || tl > ri) {
return;
} else if (le <= tl && tr <= ri) {
tree[n].c += val;
lazy[n] += val;
return;
}
push(n);
int mid = (tl + tr) / 2;
add(n * 2, tl, mid, le, ri, val);
add(n * 2 + 1, mid + 1, tr, le, ri, val);
}
inline void add(int le, int ri, lint val) {
add(1, 1, n, le, ri, val);
}
void set_line(int n, int tl, int tr, int le, int ri, Line l) {
if (tl > tr || tr < le || tl > ri) {
return;
} else if (le <= tl && tr <= ri) {
lint A = l.get(tl), B = l.get(tr), C = tree[n].get(tl), D = tree[n].get(tr);
if (A <= C && B <= D) {
tree[n] = l;
return;
} else if (A >= C && B >= D) {
return;
} else {
push(n);
int mid = (tl + tr) / 2;
if (A <= C) swap(l, tree[n]);
if (l.get(mid) >= tree[n].get(mid)) {
set_line(n * 2 + 1, mid + 1, tr, le, ri, l);
} else {
swap(l, tree[n]);
set_line(n * 2, tl, mid, le, ri, l);
}
return;
}
}
push(n);
int mid = (tl + tr) / 2;
set_line(n * 2, tl, mid, le, ri, l);
set_line(n * 2 + 1, mid + 1, tr, le, ri, l);
}
inline void set_line(int le, int ri, Line l) {
set_line(1, 1, n, le, ri, l);
}
lint query(int n, int tl, int tr, int point) {
lint ans = tree[n].get(point);
if (tl == tr) {
return ans;
}
push(n);
int mid = (tl + tr) / 2;
if (point <= mid) {
return min(ans, query(n * 2, tl, mid, point));
} else {
return min(ans, query(n * 2 + 1, mid + 1, tr, point));
}
}
inline lint query(int point) {
if (point > n || point < 1) return INF;
return query(1, 1, n, point);
}
} LS, RS; //Left side (each point represents answer of L...MaxRange) and Right side (each point represents answers to MinRange...R)
/* Sparse Table for Range Maximum Query, stores Hi and i (height and index) */
struct SparseTable {
vector<array<array<lint, 2>, 20>> sparse;
SparseTable() { }
void build(vector<lint> &H) {
lint N = H.size();
sparse.resize(N);
for (int i = 1; i < N; i++) {
sparse[i][0] = {H[i], i};
}
for (int k = 1; k < 20; k++) {
for (int i = 1; i < N; i++) {
sparse[i][k] = max(sparse[i][k], sparse[i][k - 1]);
if ((i + (1ll << (k - 1))) < N) sparse[i][k] = max(sparse[i][k], sparse[i + (1ll << (k - 1))][k - 1]);
}
}
}
inline lint query(int le, int ri) { //get index of highest mountain in range le...ri
lint k = 31 - __builtin_clz(ri - le + 1);
return (max(sparse[le][k], sparse[ri - (1 << k) + 1][k]))[1];
}
} RMQ;
void solve(int le, int ri, vector<lint> &H, vector<lint> &L, vector<lint> &R, vector<lint> &ans, vector<vector<int>> &Qs) {
if (le > ri) return;
lint m = RMQ.query(le, ri);
solve(le, m - 1, H, L, R, ans, Qs);
solve(m + 1, ri, H, L, R, ans, Qs);
for (auto i : Qs[m]) {
lint opt1, opt2;
opt1 = LS.query(L[i]) + ((R[i] - m + 1ll) * H[m]);
opt2 = ((m - L[i] + 1ll) * H[m]) + RS.query(R[i]);
ans[i] = min(opt1, opt2);
}
LS.add(le, m, (ri - m + 1ll) * H[m]);
if (ri != m) LS.set_line(le, m, LiChaoSegmentTree::Line(-H[m], LS.query(m + 1) + H[m] * (m + 1ll)));
RS.add(m, ri, (m - le + 1ll) * H[m]);
if (le != m) RS.set_line(m, ri, LiChaoSegmentTree::Line(+H[m], RS.query(m - 1) - H[m] * (m - 1ll)));
return;
}
vector<lint> minimum_costs(vector<int> h, vector<int> l, vector<int> r) {
vector<lint> H, L, R, ans;
vector<vector<int>> Qs;
lint N = h.size(), Q = l.size();
Qs.resize(N + 1), ans.resize(Q);
H.emplace_back(0);
for (int i = 0; i < N; i++) {
H.emplace_back(h[i]);
}
for (int i = 0; i < Q; i++) {
L.emplace_back(l[i] + 1);
R.emplace_back(r[i] + 1);
}
RMQ.build(H);
for (int i = 0; i < Q; i++) {
lint mx = RMQ.query(L[i], R[i] );
Qs[mx].emplace_back(i);
}
LS.build(N);
RS.build(N);
solve(1, N, H, L, R, ans, Qs);
return ans;
}
