#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint INF = 1e18;
class LiChao { // Li Chao Segment Tree
private:
struct Line { // y = ax + b
lint a, b;
lint get(lint x) { return a * x + b; }
Line() {}
Line(lint a, lint b) : a(a), b(b) {}
};
int sz;
vector<Line> tree;
vector<lint> lazy;
void Apply(int n, lint x) {
tree[n].b += x;
lazy[n] += x;
}
void Push(int n, int lc, int rc) {
Apply(lc, lazy[n]);
Apply(rc, lazy[n]);
lazy[n] = 0;
}
void SetLine(int n, int tl, int tr, int l, int r, Line line) {
if (tr < l || r < tl || tl > tr || l > r) return;
int mid = (tl + tr) / 2;
int lc = n + 1;
int rc = n + 2 * (mid - tl + 1);
if (tl != tr) Push(n, lc, rc);
if (l <= tl && tr <= r) {
if (tree[n].get(tl) > line.get(tl)) swap(tree[n], line);
if (tree[n].get(tr) <= line.get(tr)) return;
if (tree[n].get(mid) <= line.get(mid)) {
return SetLine(rc, mid + 1, tr, l, r, line);
} else {
swap(tree[n], line);
return SetLine(lc, tl, mid, l, r, line);
}
}
SetLine(lc, tl, mid, l, r, line);
SetLine(rc, mid + 1, tr, l, r, line);
}
void RangeSumUpdate(int n, int tl, int tr, int l, int r, lint x) {
if (tr < l || r < tl || tl > tr || l > r) return;
if (l <= tl && tr <= r) return Apply(n, x);
int mid = (tl + tr) / 2;
int lc = n + 1;
int rc = n + 2 * (mid - tl + 1);
Push(n, lc, rc);
RangeSumUpdate(lc, tl, mid, l, r, x);
RangeSumUpdate(rc, mid + 1, tr, l, r, x);
}
lint Query(int n, int tl, int tr, int x) {
lint res = tree[n].get(x);
if (tl == tr) return res;
int mid = (tl + tr) / 2;
int lc = n + 1;
int rc = n + 2 * (mid - tl + 1);
Push(n, lc, rc);
if (x <= mid) res = min(res, Query(lc, tl, mid, x));
if (x > mid) res = min(res, Query(rc, mid + 1, tr, x));
return res;
}
public:
LiChao() {}
LiChao(int n) : sz(n) {
tree.assign(2 * sz, Line(0, INF));
lazy.assign(2 * sz, 0);
}
void SetLine(int l, int r, lint a, lint b) {
return SetLine(1, 0, sz - 1, l, r, Line(a, b));
}
void RangeSumUpdate(int l, int r, lint x) {
return RangeSumUpdate(1, 0, sz - 1, l, r, x);
}
lint Query(int x) {
return Query(1, 0, sz - 1, x);
}
};
class SegmentTree {
private:
int sz;
vector<pair<int, int>> tree;
public:
SegmentTree() {}
SegmentTree(int n, vector<int> A) : sz(n) {
tree.resize(2 * sz);
for (int i = 0; i < sz; i++) {
tree[i + sz] = {A[i], i};
}
for (int i = sz - 1; i >= 0; i--) {
tree[i] = max(tree[i * 2], tree[i * 2 + 1]);
}
}
int Query(int l, int r) {
pair<int, int> res = {0, -1};
for (l += sz, r += sz + 1; l < r; l /= 2, r /= 2) {
if (l & 1) res = max(res, tree[l++]);
if (r & 1) res = max(res, tree[--r]);
}
return res.second;
}
};
struct query_t {
int id;
int l, r;
query_t() {}
query_t(int id, int ql, int qr) : id(id), l(ql), r(qr) {}
};
LiChao Left, Right;
SegmentTree RMQ;
void Solve(int L, int R, const vector<int> &H,
const vector<vector<query_t>> &Query, vector<lint> &Answer) {
if (L > R) return;
int M = RMQ.Query(L, R);
Solve(L, M - 1, H, Query, Answer);
Solve(M + 1, R, H, Query, Answer);
for (auto q : Query[M]) {
Answer[q.id] = min(Left.Query(q.l) + 1ll * (q.r - M + 1) * H[M],
Right.Query(q.r) + 1ll * (M - q.l + 1) * H[M]);
}
Left.RangeSumUpdate(L, M, 1ll * (R - M + 1) * H[M]);
Left.SetLine(L, M, -H[M], 1ll * M * H[M] + H[M] + (M < R ? Left.Query(M + 1) : 0));
Right.RangeSumUpdate(M, R, 1ll * (M - L + 1) * H[M]);
Right.SetLine(M, R, H[M], -1ll * M * H[M] + H[M] + (M > L ? Right.Query(M - 1) : 0));
return;
}
vector<lint> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
int N = H.size(), Q = L.size();
Left = LiChao(N);
Right = LiChao(N);
RMQ = SegmentTree(N, H);
vector<vector<query_t>> Query(N);
vector<lint> Answer(Q, INF);
for (int i = 0; i < Q; i++) {
Query[RMQ.Query(L[i], R[i])].emplace_back(i, L[i], R[i]);
}
for (int i = 0; i < N; i++) {
Left.SetLine(i, i, 0, 0);
Right.SetLine(i, i, 0, 0);
}
Solve(0, N - 1, H, Query, Answer);
return Answer;
}
