#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int const MAXN = 7.5e5+2;
ll const INF = 1e18;
struct Line {
ll a, b;
int o;
Line() = default;
Line(ll y) : a(0), b(y), o(0) {}
Line(ll a, ll b) : a(a), b(b), o(0) {}
Line(ll a, ll b, int o) : a(a), b(b), o(o) {}
ll operator()(int x) const { return a*(x-o) + b; }
bool operator==(Line const& lo) const {
return a==lo.a && b==lo.b && o == lo.o;
}
bool operator!=(Line const& lo) const {
return a!=lo.a || b!=lo.b || o != lo.o;
}
};
Line const Mixed = Line(-1);
struct {
int n;
Line ln[4*MAXN];
pair<ll, ll> meta[4*MAXN];
ll lazy[4*MAXN];
pair<ll, ll> GetMeta(int u, int L, int R) {
if (ln[u] != Mixed) return make_pair(ln[u](L), ln[u](R));
else return meta[u];
}
void Push(int u, int L, int R) {
if (!lazy[u]) return;
if (lazy[u] < 0) lazy[u] = 0;
if (ln[u] != Mixed) {
ln[u].b += lazy[u];
if (L != R) {
lazy[u*2] = lazy[u*2+1] = -1;
ln[u*2] = ln[u*2+1] = ln[u];
}
}
else {
meta[u].first += lazy[u];
meta[u].second += lazy[u];
if (L != R) {
lazy[u*2] += lazy[u];
lazy[u*2+1] += lazy[u];
}
}
lazy[u] = 0;
}
void Pull(int u, int L, int R) {
if (L == R) meta[u] = make_pair(ln[u](L), ln[u](R));
else {
if (ln[u*2] == ln[u*2+1]) ln[u] = ln[u*2];
else {
ln[u] = Mixed;
int M = (L+R)/2;
meta[u] = make_pair(GetMeta(u*2, L, M).first, GetMeta(u*2+1, M+1, R).second);
}
}
}
void Setup(int _n) {
n = _n;
memset(lazy, 0, sizeof lazy);
ln[1] = Line(INF);
lazy[1] = -1;
}
void AddRange(int u, int L, int R, int i, int j, ll val) {
Push(u, L, R);
if (i > j) return;
if (i <= L && R <= j) {
lazy[u] = val;
Push(u, L, R);
return;
}
int M = (L+R)/2;
AddRange(u*2, L, M, i, min(M,j), val);
AddRange(u*2+1, M+1, R, max(i,M+1), j, val);
Pull(u, L, R);
}
void AddRange(int l, int r, ll val) {
AddRange(1, 0, n-1, l, r, val);
}
void AssignLine(int u, int L, int R, int i, int j, Line const& line) {
Push(u, L, R);
if (i > j) return;
if (i <= L && R <= j) {
ll LeftNew = line(L), RightNew = line(R);
ll LeftOld, RightOld;
tie(LeftOld, RightOld) = GetMeta(u, L, R);
if (LeftNew <= LeftOld && RightNew <= RightOld) {
ln[u] = line; lazy[u] = -1;
Push(u, L, R);
return;
}
else if (LeftNew > LeftOld && RightNew > RightOld) return;
}
//assert(L != R);
int M = (L + R) / 2;
AssignLine(u*2, L, M, i, min(M,j), line);
AssignLine(u*2+1, M+1, R, max(M+1,i), j, line);
Pull(u, L, R);
}
void AssignLine(int l, int r, ll a, ll b, int o) {
Line _line(a,b,o);
AssignLine(1, 0, n-1, l, r, _line);
}
ll GetVal(int u, int L, int R, int idx) {
if (L == R) return ln[u](L);
if (ln[u] != Mixed) return ln[u](idx);
int M = (L+R)/2;
if (idx <= M) return GetVal(u*2, L, M, idx);
else return GetVal(u*2+1, M+1, R, idx);
}
ll GetVal(int idx) {
return GetVal(1, 0, n-1, idx);
}
} LichaoL, LichaoR;
struct {
int n;
pair<int, int> Tbl[20][MAXN];
void Setup(vector<int>& H) {
n = H.size();
for (int i = 0; i < n; ++i) {
Tbl[0][i] = make_pair(H[i], i);
}
for (int b = 1; (1<<b) <= n; ++b) {
for (int i = 0; i+(1<<b) <= n; ++i) {
Tbl[b][i] = max(Tbl[b-1][i], Tbl[b-1][i+(1<<(b-1))]);
}
}
}
int GetMax(int l, int r) {
int len = r-l+1;
int lg2 = __builtin_clz(1) - __builtin_clz(len);
int ii = max(Tbl[lg2][l], Tbl[lg2][r - (1<<lg2) +1]).second;
return ii;
}
} SparseTable;
vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R)
{
//__attribute__ ((optimize(3))) { // ?!
int n = H.size();
int q = L.size();
SparseTable.Setup(H);
LichaoL.Setup(n);
LichaoR.Setup(n);
vector<ll> AnsL(q, 0);
vector<ll> AnsR(q, 0);
vector<vector<int>> OfflineL(n);
vector<vector<int>> OfflineR(n);
for (int i = 0; i < q; ++i) {
int rt = SparseTable.GetMax(L[i], R[i]);
AnsR[i] = (ll)(rt+1-L[i]) * H[rt];
AnsL[i] = (ll)(R[i]+1-rt) * H[rt];
if (rt < R[i]) {
int rtR = SparseTable.GetMax(rt+1, R[i]);
OfflineR[rtR].emplace_back(i);
}
if (rt > L[i]) {
int rtL = SparseTable.GetMax(L[i], rt-1);
OfflineL[rtL].emplace_back(i);
}
}
function<void(int,int)> Cartesian;
Cartesian = [&](int l, int r) {
int rt = SparseTable.GetMax(l, r);
if (rt > l) Cartesian(l, rt-1);
if (rt < r) Cartesian(rt+1, r);
ll OptR = ((rt > l) ? LichaoR.GetVal(rt-1) : 0LL) + H[rt];
LichaoR.AssignLine(rt, rt, 0, OptR, 0);
if (rt < r) {
LichaoR.AddRange(rt+1, r, (ll)(rt-l+1) * H[rt]);
if (l < rt) {
LichaoR.AssignLine(rt+1, r, H[rt], OptR, rt);
}
}
for (int qi: OfflineR[rt]) {
AnsR[qi] += LichaoR.GetVal(R[qi]);
}
ll OptL = ((rt < r) ? LichaoL.GetVal(rt+1) : 0LL) + H[rt];
LichaoL.AssignLine(rt, rt, 0, OptL, 0);
if (rt > l) {
LichaoL.AddRange(l, rt-1, (ll)(r+1-rt) * H[rt]);
if (r > rt) {
LichaoL.AssignLine(l, rt-1, -H[rt], OptL + (ll)(rt-l+1)*H[rt], l);
}
}
for (int qi: OfflineL[rt]) {
AnsL[qi] += LichaoL.GetVal(L[qi]);
}
};
Cartesian(0, n-1);
for (int i = 0; i < q; ++i) AnsL[i] = min(AnsL[i], AnsR[i]);
return AnsL;
}
