#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
template <class T> using vt = vector<T>;
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)
struct Line {
ll m, c;
ll eval(const int x) {
return m * x + c;
}
};
struct Lichao {
vt<Line> st;
vt<ll> lz;
Lichao(const int n) : st(n << 2, Line{0, (ll)1e18}), lz(n << 2) {}
#define lc i << 1
#define rc lc | 1
void push(const int i) {
if (!lz[i])
return;
st[lc].c += lz[i];
lz[lc] += lz[i];
st[rc].c += lz[i];
lz[rc] += lz[i];
lz[i] = 0;
}
void update(const int ql, const int qr, Line line, const int i, const int tl, const int tr) {
if (tl > qr || tr < ql)
return;
const int tm = tl + tr >> 1;
if (ql <= tl && tr <= qr) {
if (line.eval(tm) < st[i].eval(tm))
swap(line, st[i]);
if (tl == tr)
return;
push(i);
if (line.eval(tl) < st[i].eval(tl))
update(ql, qr, line, lc, tl, tm);
if (line.eval(tr) < st[i].eval(tr))
update(ql, qr, line, rc, tm + 1, tr);
} else {
push(i);
update(ql, qr, line, lc, tl, tm);
update(ql, qr, line, rc, tm + 1, tr);
}
}
void update(const int ql, const int qr, const Line line) {
update(ql, qr, line, 1, 0, (size(st) >> 2) - 1);
}
void range_add(const int ql, const int qr, const ll v, const int i, const int tl, const int tr) {
if (tl > qr || tr < ql)
return;
if (ql <= tl && tr <= qr)
st[i].c += v, lz[i] += v;
else {
push(i);
const int tm = tl + tr >> 1;
range_add(ql, qr, v, lc, tl, tm);
range_add(ql, qr, v, rc, tm + 1, tr);
}
}
void range_add(const int ql, const int qr, const ll v) {
range_add(ql, qr, v, 1, 0, (size(st) >> 2) - 1);
}
ll query(const int x, const int i, const int tl, const int tr) {
if (tl == tr)
return st[i].eval(x);
push(i);
const int tm = tl + tr >> 1;
if (x <= tm)
return min(st[i].eval(x), query(x, lc, tl, tm));
return min(st[i].eval(x), query(x, rc, tm + 1, tr));
}
ll query(const int x) {
return query(x, 1, 0, (size(st) >> 2) - 1);
}
#undef lc
#undef rc
};
struct ST {
vt<vt<ari2>> st;
ST(const vt<int> &A) {
const int N = size(A), LOG = 31 - __builtin_clz(N);
st.resize(N, vt<ari2>(LOG + 1));
FOR(i, 0, N-1)
st[i][0] = {A[i], i};
FOR(j, 1, LOG)
FOR(i, 0, N-(1<<j))
st[i][j] = max(st[i][j-1], st[i+(1<<j-1)][j-1]);
}
int query(const int l, const int r) {
const int n = 31 - __builtin_clz(r - l + 1);
return max(st[l][n], st[r-(1<<n)+1][n])[1];
}
};
vt<ll> minimum_costs(vt<int> A, vt<int> L, vt<int> R) {
const int N = size(A);
const int Q = size(L);
ST st(A);
vt<vt<int>> queries(N);
FOR(i, 0, Q-1)
queries[st.query(L[i], R[i])].push_back(i);
vt<ll> ans(Q);
Lichao lct_left(N), lct_right(N);
auto solve = [&](auto &&self, const int l, const int r) -> void {
if (l > r)
return;
const int m = st.query(l, r);
self(self, l, m - 1);
self(self, m + 1, r);
lct_left.update(m, m, {0, 0});
lct_right.update(m, m, {0, 0});
for (const auto &qi : queries[m]) {
const ll lv = lct_left.query(L[qi]) + 1ll * (R[qi] - m + 1) * A[m];
const ll rv = lct_right.query(R[qi]) + 1ll * (m - L[qi] + 1) * A[m];
ans[qi] = min(lv, rv);
}
lct_left.range_add(l, m, 1ll * A[m] * (r - m + 1));
lct_left.update(l, m, {-A[m], lct_left.query(m+1) + 1ll * A[m] * (1 + m)});
lct_right.range_add(m, r, 1ll * A[m] * (m - l + 1));
lct_right.update(m, r, {A[m], lct_right.query(m-1) + 1ll * A[m] * (1 - m)});
};
solve(solve, 0, N - 1);
return ans;
}
