#include "meetings.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define ef emplace_front
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef double ld;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
const ld EPS = 1e-8;
ll operator * (const pll &a, const pll &b) { return a.first*b.second - b.first*a.second; }
ll ccw(const pll &a, const pll &b, const pll &c) { return a*b + b*c + c*a; }
ll lnef(ll a, ll b, ll x) { return a*x + b; }
const int MAXN = 750055;
const int MAXQ = 750055;
const int MX = 1048576;
struct MNSEG {
int d[MX*2];
void init(int dt[], int n) {
for(int i = 0; i < n; i++)
d[i+MX] = dt[i];
fill(d+MX+n, d+MX*2, INF);
for(int i = MX; --i;)
d[i] = min(d[i<<1], d[i<<1|1]);
}
int get(int s, int e) {
int r = INF; for(s += MX, e += MX; s <= e; s >>= 1, e >>= 1) {
if(s&1) { upmin(r, d[s]); s++; }
if(~e&1) { upmin(r, d[e]); e--; }
}
return r;
}
} mnseg;
struct NOD {
int s, e, m, l, r;
} nod[MAXN*2]; int nodN;
vector<int> XQV[MAXN];
int nodXI[MAXN];
pil arr[MAXN*8];
struct DEQ {
int s, e, __s;
void set(int __s) { s = e = __s*2; this->__s = __s; }
bool empty() { return s == e; }
pil& front() { return arr[s]; }
pil& back() { return arr[e-1]; }
pil& operator [] (const unsigned int a) { return arr[s+a]; }
void pop_front() { s++; }
void pop_back() { e--; }
void emplace_back(const int &a, const ll &b) { arr[e++] = pil(a, b); }
void emplace_back(const pil& p) { arr[e++] = p; }
void emplace_front(const int &a, const ll &b) { arr[--s] = pil(a, b); }
void emplace_front(const pil& p) { arr[--s] = p; }
void clear() { set(__s); }
unsigned int size() { return e-s; }
};
struct CHN {
DEQ CH;
ll delta;
int s, e;
void set(int __s, int __e) { CH.set(__s+MAXN); }
void cut(ll a, ll b) {
ll startY = lnef(a, b, s);
ll endY = lnef(a, b, e);
if(CH[0].second + delta < startY) return;
if(endY <= CH.back().second + delta) {
delta = 0;
CH.clear();
CH.eb(s, startY);
if(s != e) CH.eb(e, endY);
return;
}
int t = 0, n = sz(CH);
for(; t+1 < n && lnef(a, b, CH[t+1].first) <= CH[t+1].second + delta; t++);
ll c = (CH[t+1].second - CH[t].second) / (CH[t+1].first - CH[t].first);
ll d = CH[t].second + delta - c * CH[t].first;
int X = ld(d-b) / (a-c) + EPS;
for(; (a-c) * (X+1) <= d-b; X++);
for(; (a-c) * (X-1) >= d-b; X--);
ll Y = lnef(a, b, X);
for(int i = 0; i <= t; i++) CH.pop_front();
if(Y < lnef(c, d, X) && X+1 < CH[0].first) CH.ef(X+1, lnef(c, d, X+1) - delta);
if(s < X && X < CH[0].first) CH.ef(X, Y - delta);
if(s < CH[0].first) CH.ef(s, startY - delta);
}
void mergeback(CHN &v) {
ll dt = -delta + v.delta;
for(int i = 0, n = sz(v.CH); i < n; i++)
CH.eb(v.CH[i].first, v.CH[i].second + dt);
e = v.e;
}
void mergefront(CHN &v) {
ll dt = -delta + v.delta;
for(int i = sz(v.CH); i--;)
CH.ef(v.CH[i].first, v.CH[i].second + dt);
s = v.s;
}
ll get(int X) {
if(s == e) return CH[0].second + delta;
int ls = 0, le = sz(CH)-2; for(int m; ls < le;) {
m = (ls + le + 1) >> 1;
if(CH[m].first <= X && X <= CH[m+1].first) {
ls = m;
break;
}
if(X < CH[m].first) le = m-1;
else ls = m;
}
ll a = (CH[ls+1].second - CH[ls].second) / (CH[ls+1].first - CH[ls].first);
ll b = CH[ls].second + delta - a * CH[ls].first;
return lnef(a, b, X);
}
};
int H[MAXN], HO[MAXN], HRO[MAXN];
int A[MAXQ], B[MAXQ], C[MAXQ];
int QS[MAXQ], QE[MAXQ];
ll Ans[MAXQ], preAns[MAXQ];
int N, Q;
int makeTree(int s, int e) {
nodN++; int idx = nodN;
if(!nodXI[s]) nodXI[s] = idx;
nod[idx].s = s;
nod[idx].e = e;
if(s == e) return idx;
nod[idx].m = HO[mnseg.get(s+1, e)];
nod[idx].l = makeTree(s, nod[idx].m-1);
nod[idx].r = makeTree(nod[idx].m, e);
return idx;
}
void makeTree() {
nodN = 0;
fill(nodXI, nodXI+MAXN, 0);
for(int i = 0; i < MAXN; i++) XQV[i].clear();
for(int i = 1; i <= Q; i++) XQV[QS[i]].eb(i);
makeTree(0, N);
}
void calTree(CHN &chn, int idx) {
auto &v = nod[idx];
chn.set(v.s, v.e);
if(v.s == v.e) {
chn.CH.eb(v.s, H[v.s]);
chn.delta = 0;
chn.s = v.s;
chn.e = v.e;
} else {
CHN chnR;
calTree(chn, v.l);
calTree(chnR, v.r);
chnR.delta += H[v.s] + ll(v.m - v.s - 1) * H[v.m];
chnR.cut(H[v.m], chn.CH.back().second + chn.delta + ll(-v.m + 1) * H[v.m]);
if(sz(chn.CH) < sz(chnR.CH)) {
chnR.mergefront(chn);
swap(chn, chnR);
} else chn.mergeback(chnR);
chnR.CH.clear();
}
if(nodXI[v.s] == idx) {
for(int qi : XQV[v.s]) {
preAns[qi] = chn.get(QE[qi]);
}
}
}
void process() {
H[0] = INF;
iota(HO+1, HO+N+1, 1);
sort(HO+1, HO+N+1, [&](int a, int b) {
if(H[a] != H[b]) return H[a] > H[b];
return a < b;
});
for(int i = 0; i <= N; i++) HRO[HO[i]] = i;
mnseg.init(HRO, N+1);
for(int i = 1; i <= Q; i++) {
C[i] = HO[mnseg.get(A[i], B[i])];
QS[i] = C[i];
QE[i] = B[i];
}
makeTree();
{ CHN chn; calTree(chn, 1); }
for(int i = 1; i <= Q; i++) {
Ans[i] = preAns[i] + ll(C[i] - A[i]) * H[C[i]];
}
reverse(H+1, H+N+1);
for(int i = 1; i <= N; i++) HO[i] = N+1 - HO[i];
for(int i = 1; i <= N; i++) HRO[HO[i]] = i;
mnseg.init(HRO, N+1);
for(int i = 1; i <= Q; i++) {
A[i] = N+1 - A[i];
B[i] = N+1 - B[i];
swap(A[i], B[i]);
C[i] = N+1 - C[i];
QS[i] = C[i];
QE[i] = B[i];
}
makeTree();
{ CHN chn; calTree(chn, 1); }
for(int i = 1; i <= Q; i++) {
ll t = preAns[i] + ll(C[i] - A[i]) * H[C[i]];
if(t < Ans[i]) Ans[i] = t;
}
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R) {
::N = sz(H);
::Q = sz(L);
for(int i = 1; i <= Q; i++) {
::A[i] = L[i-1] + 1;
::B[i] = R[i-1] + 1;
}
for(int i = 1; i <= N; i++) {
::H[i] = H[i-1];
}
process();
vector<ll> V;
for(int i = 1; i <= Q; i++) V.eb(Ans[i]);
return V;
}
