#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
struct query {
int id = 0;
int pos = 0;
long long off = 0;
query(int _id, int _pos, long long _off): id(_id), pos(_pos), off(_off) {};
};
struct node {
int pos = 0;
int rangeL = 0;
int rangeR = 0;
int sz = 0;
long long off = 0;
node *left = nullptr;
node *right = nullptr;
vector<query> queries;
node(int _pos, int _rangeL, int _rangeR, node *_left, node *_right): pos(_pos), rangeL(_rangeL), rangeR(_rangeR), left(_left), right(_right) {};
};
struct line {
int lt = 0;
int rt = 0;
long long a = 0;
long long b = 0;
line(int _lt, int _rt, long long _a, long long _b): lt(_lt), rt(_rt), a(_a), b(_b) {};
long long eval(int x) {
return a * (x - lt) + b;
}
};
const long long inf = 1e18L + 20;
const int maxN = 7.5e5 + 20;
const int maxK = 20;
int lg[maxN];
pair<pair<int, int>, int> sparse[maxN][maxK];
pair<int, int> H[maxN];
node *nodes[maxN];
int L[maxN];
int R[maxN];
vector<long long> res;
int N, Q;
int get(int lt, int rt) {
int k = lg[rt - lt + 1];
return max(sparse[lt][k], sparse[rt - (1 << k) + 1][k]).second;
}
node *build(int lt, int rt) {
if (lt > rt) {
return nullptr;
}
int mx = get(lt, rt);
nodes[mx] = new node(mx, lt, rt, build(lt, mx - 1), build(mx + 1, rt));
return nodes[mx];
}
map<int, line*> lines;
void calc(node *cur) {
long long left_cost = 0;
if (cur->left) {
calc(cur->left);
cur->off = cur->left->off;
cur->sz = cur->left->sz;
left_cost = prev(lines.upper_bound(cur->pos - 1))->second->eval(cur->pos - 1) + cur->left->off;
}
cur->sz++;
line *mid = new line(cur->pos, cur->rangeR, H[cur->pos].first, left_cost + H[cur->pos].first - cur->off);
lines[cur->pos] = mid;
if (cur->right) {
calc(cur->right);
cur->right->off += 1LL * H[cur->pos].first * (cur->pos - cur->rangeL + 1);
auto it = next(lines.find(cur->pos));
while (it != lines.end() && it->first <= cur->rangeR) {
if (mid->eval(it->second->rt) + cur->off <= it->second->eval(it->second->rt) + cur->right->off) {
it = lines.erase(it);
cur->right->sz--;
}
else {
break;
}
}
if (it != lines.end() && it->first <= cur->rangeR) {
int lt = it->second->lt;
int rt = it->second->rt - 1;
int last = lt - 1;
while (lt <= rt) {
int mt = (lt + rt) / 2;
if (mid->eval(mt) + cur->off <= it->second->eval(mt) + cur->right->off) {
last = mt;
lt = mt + 1;
}
else {
rt = mt - 1;
}
}
mid->rt = last;
it->second->b = it->second->eval(mid->rt + 1);
it->second->lt = mid->rt + 1;
lines[it->second->lt] = it->second;
it = lines.erase(it);
}
if (cur->sz >= cur->right->sz) {
while (it != lines.end() && it->first <= cur->rangeR) {
it->second->b -= cur->off - cur->right->off;
it++;
}
}
else {
it = lines.find(cur->rangeL);
while (it != lines.end() && it->first <= cur->pos) {
it->second->b -= cur->right->off - cur->off;
it++;
}
cur->off = cur->right->off;
}
cur->sz += cur->right->sz;
}
for (auto q: cur->queries) {
res[q.id] = min(res[q.id], prev(lines.upper_bound(q.pos))->second->eval(q.pos) + cur->off + q.off);
}
}
void solve() {
for (int i = 0; i < N; i++) {
sparse[i][0] = make_pair(H[i], i);
}
for (int k = 1; k < maxK; k++) {
for (int i = 0; i + (1 << k) <= N; i++) {
sparse[i][k] = max(sparse[i][k - 1], sparse[i + (1 << (k - 1))][k - 1]);
}
}
node *root = build(0, N - 1);
for (int i = 0; i < Q; i++) {
int mx = get(L[i], R[i]);
res[i] = min(res[i], 1LL * H[mx].first * (R[i] - L[i] + 1));
if (mx < R[i]) {
nodes[mx]->right->queries.emplace_back(i, R[i], 1LL * H[mx].first * (mx - L[i] + 1));
}
}
lines.clear();
calc(root);
}
vector<long long> minimum_costs(vector<int> _H, vector<int> _L, vector<int> _R) {
for (int i = 2; i < maxN; i++) {
lg[i] = lg[i / 2] + 1;
}
N = _H.size();
for (int i = 0; i < N; i++) {
H[i] = make_pair(_H[i], i);
}
Q = _L.size();
for (int i = 0; i < Q; i++) {
L[i] = _L[i];
R[i] = _R[i];
}
res.resize(Q, inf);
for (int iter = 0; iter < 2; iter++) {
solve();
reverse(H, H + N);
for (int i = 0; i < Q; i++) {
L[i] = N - 1 - L[i];
R[i] = N - 1 - R[i];
swap(L[i], R[i]);
}
}
return res;
}
