#include "meetings.h"
#include <functional>
using ll = long long;
struct segT
{
struct data
{
int st, en;
ll val_l, val_r, k, b;
bool cov;
data(ll _k = 0, ll _b = 0, bool flg = false) : k(_k), b(_b), cov(flg) {}
inline void paint(data x)
{
if (x.cov)
{
val_l = val_r = k = b = 0;
cov = true;
}
k += x.k;
b += x.b;
val_l += x.k * st + x.b;
val_r += x.k * en + x.b;
}
} seg[3000005];
int n;
inline void push_down(int u)
{
if (seg[u].cov || seg[u].k || seg[u].b)
{
seg[u << 1].paint(seg[u]);
seg[u << 1 | 1].paint(seg[u]);
seg[u].k = seg[u].b = 0;
seg[u].cov = false;
}
}
inline void push_up(int u)
{
seg[u].val_l = seg[u << 1].val_l;
seg[u].val_r = seg[u << 1 | 1].val_r;
}
void build(int u, int l, int r)
{
seg[u].st = l;
seg[u].en = r;
if (l == r)
return;
int m = l + r >> 1;
build(u << 1, l, m);
build(u << 1 | 1, m + 1, r);
}
void modify(int u, int l, int r, int L, int R, ll x)
{
if (L <= l && r <= R)
{
seg[u].paint({0, x});
return;
}
push_down(u);
int m = l + r >> 1;
if (L <= m)
modify(u << 1, l, m, L, R, x);
if (m < R)
modify(u << 1 | 1, m + 1, r, L, R, x);
push_up(u);
}
void add_line(int u, int l, int r, int L, int R, ll k, ll b)
{
if (L <= l && r <= R)
{
ll new_l = k * l + b, new_r = k * r + b;
if (new_l >= seg[u].val_l && new_r >= seg[u].val_r)
return;
if (new_l <= seg[u].val_l && new_r <= seg[u].val_r)
{
seg[u].paint({k, b, true});
return;
}
}
push_down(u);
int m = l + r >> 1;
if (L <= m)
add_line(u << 1, l, m, L, R, k, b);
if (m < R)
add_line(u << 1 | 1, m + 1, r, L, R, k, b);
push_up(u);
}
ll query(int u, int l, int r, int pos)
{
if (l == r)
return seg[u].val_l;
push_down(u);
int m = l + r >> 1;
if (pos <= m)
return query(u << 1, l, m, pos);
return query(u << 1 | 1, m + 1, r, pos);
}
inline void init(int _n)
{
n = _n;
build(1, 0, n - 1);
}
inline void modify(int L, int R, ll x) { modify(1, 0, n - 1, L, R, x); }
inline void add_line(int L, int R, ll k, ll b) { add_line(1, 0, n - 1, L, R, k, b); }
inline ll query(int pos) { return query(1, 0, n - 1, pos); }
} pre, suf;
std::vector<ll> minimum_costs(std::vector<int> arr, std::vector<int> ql, std::vector<int> qr)
{
int n = arr.size(), q = ql.size();
std::vector<int> lg(n + 1);
for (int i = 2; i <= n; i++)
lg[i] = lg[i >> 1] + 1;
std::vector<std::vector<int> > mx(lg[n] + 1, std::vector<int>(n));
for (int i = 0; i < n; i++)
mx[0][i] = i;
auto larger = [&] (int x, int y) { return arr[x] > arr[y] ? x : y; };
for (int i = 1; i <= lg[n]; i++)
{
for (int j = 0; j + (1 << i) <= n; j++)
mx[i][j] = larger(mx[i - 1][j], mx[i - 1][j + (1 << i - 1)]);
}
auto query = [&] (int l, int r)
{
int len = lg[r - l + 1];
return larger(mx[len][l], mx[len][r - (1 << len) + 1]);
};
std::vector<ll> ans(q);
std::vector<std::vector<int> > qry(n);
for (int i = 0; i < q; i++)
qry[query(ql[i], qr[i])].push_back(i);
pre.init(n);
suf.init(n);
std::function<void (int, int)> solve = [&] (int l, int r)
{
if (l > r)
return;
int m = query(l, r);
solve(l, m - 1);
solve(m + 1, r);
for (auto i : qry[m])
{
ans[i] = (ll)arr[m] * (qr[i] - ql[i] + 1);
if (ql[i] < m)
ans[i] = std::min(suf.query(ql[i]) + (ll)arr[m] * (qr[i] - m + 1), ans[i]);
if (m < qr[i])
ans[i] = std::min(pre.query(qr[i]) + (ll)arr[m] * (m - ql[i] + 1), ans[i]);
}
ll val_pre = arr[m] + (l < m ? pre.query(m - 1) : 0),
val_suf = arr[m] + (m < r ? suf.query(m + 1) : 0);
pre.modify(m, m, val_pre);
suf.modify(m, m, val_suf);
if (l < m)
{
suf.modify(l, m - 1, (ll)arr[m] * (r - m + 1));
suf.add_line(l, m - 1, -arr[m], val_suf + (ll)arr[m] * m);
}
if (m < r)
{
pre.modify(m + 1, r, (ll)arr[m] * (m - l + 1));
pre.add_line(m + 1, r, arr[m], val_pre - (ll)arr[m] * m);
}
};
solve(0, n - 1);
return ans;
}
