#include "meetings.h"
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define lint long long
#define SZ 1048576
#define N_ 751000
vector<lint>Res;
int w[N_], PV[N_], XX[N_], QL[N_], QR[N_];
int n, Q;
struct Query {
int x, y, num;
bool operator < (const Query &p)const {
return x < p.x;
}
}QQ[N_];
struct Tree {
struct T1{
lint AK, BK, AA, BB, CK;
void Add(lint A, lint B) {
AK += A;
AA += A;
BK += B;
BB += B;
}
void Clear() {
AK = BK = AA = BB = 0;
CK = 1;
}
}L, R;
}IT[SZ + SZ];
void Add2(int nd, lint A1, lint B1, lint A2, lint B2) {
IT[nd].L.Add(A1, B1);
IT[nd].R.Add(A2, B2);
}
void Spread(int nd) {
if (IT[nd].L.CK) {
IT[nd * 2].L.Clear();
IT[nd * 2 + 1].L.Clear();
IT[nd].L.CK = 0;
}
if (IT[nd].R.CK) {
IT[nd * 2].R.Clear();
IT[nd * 2 + 1].R.Clear();
IT[nd].R.CK = 0;
}
Add2(nd * 2, IT[nd].L.AK, IT[nd].L.BK, IT[nd].R.AK, IT[nd].R.BK);
Add2(nd * 2 + 1, IT[nd].L.AK, IT[nd].L.BK, IT[nd].R.AK, IT[nd].R.BK);
IT[nd].L.AK = IT[nd].L.BK = IT[nd].R.AK = IT[nd].R.BK = 0;
}
void UDT(int nd) {
IT[nd].L.AA = IT[nd * 2].L.AA;
IT[nd].L.BB = IT[nd * 2].L.BB;
IT[nd].R.AA = IT[nd * 2 + 1].R.AA;
IT[nd].R.BB = IT[nd * 2 + 1].R.BB;
}
void Add(int nd, int b, int e, int s, int l, lint A1, lint B1, lint A2, lint B2) {
if (s > l)return;
if (b == s && e == l) {
Add2(nd, A1, B1, A2, B2);
return;
}
int m = (b + e) >> 1;
Spread(nd);
if(s <= m)Add(nd * 2, b, m, s, min(m, l), A1, B1, A2, B2);
if(l > m)Add(nd * 2 + 1, m + 1, e, max(m + 1, s), l, A1, B1, A2, B2);
UDT(nd);
}
void Wipe(int nd, int b, int e, int s, int l, int ck) {
if (s > l)return;
if (b == s && e == l) {
if (ck == 0)IT[nd].L.Clear();
else IT[nd].R.Clear();
return;
}
int m = (b + e) >> 1;
Spread(nd);
Wipe(nd * 2, b, m, s, min(m, l), ck);
Wipe(nd * 2 + 1, m + 1, e, max(m + 1, s), l, ck);
UDT(nd);
}
lint Calc(int nd, int b, int e, int x, int ck) {
if (b == e) {
if (ck == 0)return IT[nd].L.AA*x + IT[nd].L.BB;
else return IT[nd].R.AA*x + IT[nd].R.BB;
}
int m = (b + e) >> 1;
Spread(nd);
if (x <= m)return Calc(nd * 2, b, m, x, ck);
else return Calc(nd * 2 + 1, m + 1, e, x, ck);
}
int Rres, Lres;
void GetRight(int nd, int b, int e, int s, int l, lint M) {
if (b == e) {
if (IT[nd].R.AA * e + IT[nd].R.BB >= M)Rres = e;
return;
}
int m = (b + e) >> 1;
Spread(nd);
if (l <= m)return GetRight(nd * 2, b, m, s, l, M);
if (s > m)return GetRight(nd * 2 + 1, m + 1, e, s, l, M);
if (IT[nd * 2].R.AA * m + IT[nd * 2].R.BB >= M) {
Rres = m;
GetRight(nd * 2, b, m, s, m, M);
}
else {
GetRight(nd * 2 + 1, m + 1, e, m + 1, l, M);
}
}
void GetLeft(int nd, int b, int e, int s, int l, lint M) {
if (b == e) {
if (IT[nd].L.AA * e + IT[nd].L.BB >= M)Lres = e;
return;
}
int m = (b + e) >> 1;
Spread(nd);
if (l <= m)return GetLeft(nd * 2, b, m, s, l, M);
if (s > m)return GetLeft(nd * 2 + 1, m + 1, e, s, l, M);
if (IT[nd * 2 + 1].L.AA * (m + 1) + IT[nd * 2 + 1].L.BB >= M) {
Lres = m + 1;
GetLeft(nd * 2 + 1, m + 1, e, m + 1, l, M);
}
else {
GetLeft(nd * 2, b, m, s, m, M);
}
}
int GetRight2(int s, int l, lint M) {
Rres = l + 1;
GetRight(1, 1, n, s, l, M);
return Rres;
}
int GetLeft2(int s, int l, lint M) {
Lres = s - 1;
GetLeft(1, 1, n, s, l, M);
return Lres;
}
void Make(int s, int l, lint g, int ck) {
Wipe(1, 1, n, s, l, ck);
if(ck == 0)Add(1, 1, n, s, l, 0, g, 0, 0);
else Add(1, 1, n, s, l, 0, 0, 0, g);
}
struct RMQ {
int IT[SZ + SZ];
void Put(int a, int h) {
a += SZ;
IT[a] = h;
while (a != 1) {
a >>= 1;
IT[a] = max(IT[a * 2], IT[a * 2 + 1]);
}
}
int Find(int b, int e) {
int r = -1, pv = 0;
b += SZ, e += SZ;
while (b <= e) {
if (r < IT[b])r = IT[b], pv = b;
if (r < IT[e])r = IT[e], pv = e;
b = (b + 1) >> 1, e = (e - 1) >> 1;
}
while (pv < SZ) {
pv *= 2;
if (IT[pv] != r)pv++;
}
return pv - SZ;
}
}HH, TP;
int Do(int b, int e) {
int m = HH.Find(b, e);
int ret = w[m];
lint M = w[m], LM = 0, RM = 0;
if (b != m) {
LM = Do(b, m - 1);
}
if (e != m) {
RM = Do(m + 1, e);
}
int p1 = lower_bound(XX, XX + Q, m) - XX;
int p2 = lower_bound(XX, XX + Q, e + 1) - XX;
while (p1 < p2) {
int t = TP.Find(p1, p2 - 1);
if (TP.IT[t + SZ] < b)break;
int x = QQ[t].num;
TP.Put(t, 0);
int bb = QL[x], ee = QR[x];
lint rr = 0;
if (bb != m) {
rr = max(rr, (M - LM) * (m - bb) + Calc(1, 1, n, bb, 0));
}
if (ee != m) {
rr = max(rr, (M - RM) * (ee - m) + Calc(1, 1, n, ee, 1));
}
Res[x] = M * (ee - bb + 1) - rr;
}
Add(1, 1, n, m + 1, e, -(M - RM), (e + 1) * (M - RM), (M - RM), -m * (M - RM));
Add(1, 1, n, b, m - 1, -(M - LM), m * (M - LM), (M - LM), -(b - 1) * (M - LM));
if (e > m) {
lint Lg = Calc(1, 1, n, m + 1, 0);
int pv;
if (b < m)pv = GetLeft2(b, m - 1, Lg);
else pv = m - 1;
Make(pv + 1, m, Lg, 0);
}
if (b < m) {
lint Rg = Calc(1, 1, n, m - 1, 1);
int pv;
if (e > m)pv = GetRight2(m + 1, e, Rg);
else pv = m + 1;
Make(m, pv - 1, Rg, 1);
}
return ret;
}
std::vector<lint> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R) {
Q = L.size();
n = H.size();
int i;
Res.resize(Q);
for (i = 0; i < Q; i++) {
QQ[i] = { R[i] + 1,L[i] + 1,i };
QL[i] = L[i] + 1, QR[i] = R[i] + 1;
}
sort(QQ, QQ + Q);
for (i = 0; i < Q; i++)XX[i] = QQ[i].x;
for (i = 0; i < n; i++)w[i + 1] = H[i];
for (i = 1; i <= n; i++) {
HH.Put(i, w[i]);
}
for (i = 0; i < Q; i++) {
TP.Put(i, QQ[i].y);
}
Do(1, n);
return Res;
}
