#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll inf = 3e18;
struct segtree {
segtree *left{}, *right{};
ll lazy_k = -228, lazy_b = 0, first = 0, last = 0;
//pushed line, value in first point, value in last point
//if (k == -228) then this is just add b
void apply(ll k, ll b, int l, int r) {
if (k == -228) {
lazy_b += b;
first += b;
last += b;
} else {
lazy_k = k, lazy_b = b;
first = k * l + b;
last = k * (r - 1) + b;
}
}
void push(int l, int r) {
if (!left) {
left = new segtree(), right = new segtree();
}
int mid = (l + r) >> 1;
left->apply(lazy_k, lazy_b, l, mid);
right->apply(lazy_k, lazy_b, mid, r);
lazy_k = -228, lazy_b = 0;
}
void pull() {
first = left->first;
last = right->last;
}
void update(int l, int r, ll a, ll k, ll b, int lx, int rx) {
if (l >= rx || lx >= r) {
return;
} else if (l <= lx && rx <= r) {
if (first + a <= k * lx + b) {
apply(-228, a, lx, rx);
return;
} else if (last + a >= k * (rx - 1) + b) {
apply(k, b, lx, rx);
return;
}
}
int mid = (lx + rx) >> 1;
push(lx, rx);
left->update(l, r, a, k, b, lx, mid);
right->update(l, r, a, k, b, mid, rx);
pull();
}
ll query(int i, int lx, int rx) {
if (lx + 1 == rx) {
return first;
} else {
push(lx, rx);
int mid = (lx + rx) >> 1;
if (i < mid) {
return left->query(i, lx, mid);
} else {
return right->query(i, mid, rx);
}
}
}
};
vector<ll> minimum_costs(vector<int> h, vector<int> L, vector<int> R) {
int n = (int) h.size();
int q = (int) L.size();
vector<ll> ans(q, inf);
for (int _ = 0; _ < 2; ++_) {
int logn = __lg(n) + 1;
vector<vector<pair<int, int>>> sp(logn);
for (int l = 0; l < logn; ++l) {
sp[l].resize(n - (1 << l) + 1);
for (int i = 0; i <= n - (1 << l); ++i) {
if (l == 0) {
sp[l][i] = {h[i], -i};
} else {
sp[l][i] = max(sp[l - 1][i], sp[l - 1][i + (1 << (l - 1))]);
}
}
}
auto get_max = [&](int l, int r) {
assert(r > l && l >= 0 && r <= n);
int lg = __lg(r - l);
return max(sp[lg][l], sp[lg][r - (1 << lg)]);
};
vector adj(n, array<int, 2>{-1, -1});
vector<vector<array<int, 3>>> queries(n);
vector<int> right(n), left(n);
vector<int> stk;
int root = -1;
for (int i = 0; i < n; ++i) {
while (!stk.empty() && h[stk.back()] < h[i]) {
stk.pop_back();
}
if (!stk.empty()) {
adj[i][0] = adj[stk.back()][1];
adj[stk.back()][1] = i;
} else {
adj[i][0] = root;
root = i;
}
stk.push_back(i);
}
for (int i = 0; i < q; ++i) {
auto [hight, j] = get_max(L[i], R[i] + 1);
j = -j;
queries[j].push_back({L[i], R[i], i});
}
auto *t = new segtree();
function<void(int)> dfs = [&](int v) {
for (int to: adj[v]) {
if (to != -1) {
dfs(to);
}
}
ll mx = h[v];
for (auto [l, r, i]: queries[v]) {
ans[i] = min(ans[i], (v - l + 1) * mx + (r == v ? 0 : t->query(r, 0, n)));
}
int l = adj[v][0] == -1 ? v : left[adj[v][0]];
int r = adj[v][1] == -1 ? v : right[adj[v][1]];
left[v] = l, right[v] = r;
t->update(v, r + 1, mx * (v - l + 1), h[v], (l == v ? 0 : t->query(v - 1, 0, n)) - mx * (v - 1), 0, n);
};
dfs(root);
reverse(h.begin(), h.end());
for (int i = 0; i < q; ++i) {
L[i] = n - L[i] - 1;
R[i] = n - R[i] - 1;
swap(L[i], R[i]);
}
}
return ans;
}
