#include "meetings.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <set>
#pragma GCC optimize("O3")
#define debug(x) #x << " = " << x << '\n'
using ll = long long;
const ll INF = 1e18;
const ll ALMOSTINF = 1e14;
struct RMQ {
int n;
std::vector<int> a;
std::vector<std::vector<int>> rmq;
std::vector<int> lg2;
int myMax(int x, int y) {
if (a[x] == a[y]) {
return x < y? x : y;
}
return a[x] >= a[y]? x : y;
}
RMQ() {}
void build(const std::vector<int> &_a) {
a = _a;
n = (int) a.size();
lg2.resize(n + 1);
lg2[1] = 0;
for (int i = 2; i <= n; i++) {
lg2[i] = lg2[i >> 1] + 1;
}
int sz = std::__lg(n);
rmq = std::vector<std::vector<int>>(sz + 1, std::vector<int>(n, n));
for (int i = 0; i < n; i++) {
rmq[0][i] = i;
}
for (int j = 1; j <= sz; j++) {
for (int i = 0; i + (1 << j) - 1 < n; i++) {
rmq[j][i] = myMax(rmq[j - 1][i], rmq[j - 1][i + (1 << (j - 1))]);
}
}
}
int query(int l, int r) {
int k = lg2[r - l + 1];
return myMax(rmq[k][l], rmq[k][r - (1 << k) + 1]);
}
};
struct LiChao {
struct Line {
ll a, b;
Line() {}
Line(ll x, ll y) : a(x), b(y) {}
Line operator + (const Line &other) const {
return Line(a + other.a, b + other.b);
}
ll eval(ll x) {
return (ll) a * x + b;
}
};
struct Node {
Line L;
ll lazy;
Node() {
L = {0, +INF};
lazy = 0;
}
};
LiChao() {}
int n;
std::vector<Node> aint;
void init(int _n) {
n = _n;
aint.resize(4 * n + 1);
for (int i = 0; i < (int) aint.size(); i++) {
aint[i] = Node();
}
}
void pushLazy(int node, int tl, int tr) {
if (tl != tr && aint[node].lazy != 0) {
aint[2 * node].lazy = aint[2 * node].lazy + aint[node].lazy;
aint[2 * node + 1].lazy = aint[2 * node + 1].lazy + aint[node].lazy;
}
aint[node].L.b = aint[node].L.b + aint[node].lazy;
aint[node].lazy = 0;
}
void insertLine(int node, int tl, int tr, Line L) {
if (L.b >= ALMOSTINF) {
return;
}
pushLazy(node, tl, tr);
int mid = (tl + tr) / 2;
if (L.eval(mid) < aint[node].L.eval(mid)) {
std::swap(aint[node].L, L);
}
if (tl == tr) {
return;
}
if (L.eval(tl) < aint[node].L.eval(tl)) {
insertLine(2 * node, tl, mid, L);
} else {
insertLine(2 * node + 1, mid + 1, tr, L);
}
}
void pushLine(int node, int tl, int tr) {
if (tl < tr) {
int mid = (tl + tr) / 2;
insertLine(2 * node, tl, mid, aint[node].L);
insertLine(2 * node + 1, mid + 1, tr, aint[node].L);
}
aint[node].L = {0, +INF};
}
void addConstant(int node, int tl, int tr, int l, int r, ll c) {
if (l <= tl && tr <= r) {
aint[node].lazy += c;
} else {
pushLazy(node, tl, tr);
pushLine(node, tl, tr);
int mid = (tl + tr) / 2;
if (l <= mid) {
addConstant(2 * node, tl, mid, l, r, c);
}
if (mid < r) {
addConstant(2 * node + 1, mid + 1, tr, l, r, c);
}
}
}
void minLine(int node, int tl, int tr, int l, int r, Line L) {
pushLazy(node, tl, tr);
if (l <= tl && tr <= r) {
insertLine(node, tl, tr, L);
} else {
int mid = (tl + tr) / 2;
if (l <= mid) {
minLine(2 * node, tl, mid, l, r, L);
}
if (mid < r) {
minLine(2 * node + 1, mid + 1, tr, l, r, L);
}
}
}
ll pointQuery(int node, int tl, int tr, int p) {
pushLazy(node, tl, tr);
if (tl == tr) {
return aint[node].L.eval(p);
}
int mid = (tl + tr) / 2;
if (p <= mid) {
return std::min(aint[node].L.eval(p), pointQuery(2 * node, tl, mid, p));
} else {
return std::min(aint[node].L.eval(p), pointQuery(2 * node + 1, mid + 1, tr, p));
}
}
void addConstant(int l, int r, ll c) {
if (l > r) {
return;
}
addConstant(1, 0, n - 1, l, r, c);
}
void minLine(int l, int r, ll x, ll y) {
if (l > r) {
return;
}
minLine(1, 0, n - 1, l, r, Line(x, y));
}
ll pointQuery(int p) {
return pointQuery(1, 0, n - 1, p);
}
void pointUpdate(int p, ll v) {
addConstant(p, p, v - pointQuery(p));
}
};
std::vector<ll> minimum_costs(std::vector<int> a, std::vector<int> L, std::vector<int> R) {
int n = (int) a.size();
int q = (int) L.size();
std::vector<ll> answer(q, +INF);
LiChao DS;
RMQ rmq;
std::vector<std::vector<int>> queries(n);
auto solve = [&](auto &&self, int l, int r) -> void {
if (l > r) {
return;
}
int p = rmq.query(l, r);
self(self, l, p - 1);
self(self, p + 1, r);
// raspund la query uri
for (int index : queries[p]) {
answer[index] = std::min(answer[index], DS.pointQuery(R[index]) + (ll) a[p] * (p - L[index] + 1));
}
// acum trebuie sa recalculez pref[l..r]
// pref[l..p-1] ramane la fel
// pref[p]
ll c = p == l? 0 : DS.pointQuery(p - 1);
DS.pointUpdate(p, c + a[p]);
// // pref[p+1..r]
DS.addConstant(p + 1, r, (ll) a[p] * (p - l + 1));
DS.minLine(p + 1, r, a[p], c + (ll) a[p] * (-p + 1));
};
auto addQueries = [&]() {
for (int i = 0; i < n; i++) {
queries[i].clear();
}
for (int i = 0; i < q; i++) {
queries[rmq.query(L[i], R[i])].push_back(i);
}
};
auto prepare = [&]() {
DS.init(n);
for (int i = 0; i < n; i++) {
DS.pointUpdate(i, 0);
}
rmq.build(a);
addQueries();
};
prepare();
solve(solve, 0, n - 1);
std::reverse(a.begin(), a.end());
for (int i = 0; i < q; i++) {
L[i] = n - 1 - L[i];
R[i] = n - 1 - R[i];
std::swap(L[i], R[i]);
}
prepare();
solve(solve, 0, n - 1);
return answer;
}
