#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
template <class T> using vt = vector<T>;
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)
ari2 operator+(const ari2 &a, const ari2 &b) {
return {min(a[0], b[0]), min(a[1], b[1])};
}
struct Node {
int v1; ari2 v2;
Node operator+(const Node &other) {
return {min(v1, other.v1), v2 + other.v2};
}
};
struct ST {
const int N;
vt<Node> st;
ST(const int n) : N(n), st(n << 1, {INT_MAX, ari2{INT_MAX, INT_MAX}}) {}
void update(int i, const Node v) {
i += N;
st[i] = st[i] + v;
while (i >>= 1)
st[i] = st[i<<1] + st[i<<1|1];
}
Node query(int l, int r) {
Node ret = {INT_MAX, ari2{INT_MAX, INT_MAX}};
for (l += N, r += N+1; l < r; l >>= 1, r >>= 1) {
if (l & 1)
ret = ret + st[l++];
if (r & 1)
ret = ret + st[--r];
}
return ret;
}
};
vt<ll> calculate_costs(vt<int> W, vt<int> A, vt<int> B, vt<int> E) {
const int N = size(W), Q = size(E);
if (N == 1)
return vt<ll>(Q, A[0]);
ll sum = 0;
{
vt<int> ord(N);
iota(all(ord), 0);
sort(all(ord), [&](const int &a, const int &b) {
return W[a] < W[b];
});
vt<int> _W(N), _A(N), _B(N);
FOR(i, 0, N-1) {
_W[i] = W[ord[i]];
_A[i] = A[ord[i]];
_B[i] = B[ord[i]];
sum += B[i];
}
W = _W, A = _A, B = _B;
#ifdef DEBUG
cout << "W: ";
FOR(i, 0, N-1)
cout << W[i] << "\n "[i+1<N];
cout << "A: ";
FOR(i, 0, N-1)
cout << A[i] << "\n "[i+1<N];
cout << "B: ";
FOR(i, 0, N-1)
cout << B[i] << "\n "[i+1<N];
#endif
}
vt<int> sweep(N-1);
iota(all(sweep), 0);
sort(all(sweep), [&](const int &a, const int &b) {
return W[a+1] - W[a] < W[b+1] - W[b];
});
vt<int> sweep2(N-2);
iota(all(sweep2), 0);
sort(all(sweep2), [&](const int &a, const int &b) {
return W[a+2] - W[a] < W[b+2] - W[b];
});
vt<int> ord(Q);
iota(all(ord), 0);
sort(all(ord), [&](const int &a, const int &b) {
return E[a] < E[b];
});
ST st(N);
FOR(i, 0, N-1)
st.update(i, Node{INT_MAX, ari2{i & 1 ? INT_MAX : A[i] - B[i], i & 1 ? A[i] - B[i] : INT_MAX}});
vt<int> L(N), R(N);
iota(all(L), 0);
iota(all(R), 0);
const auto cost = [&](const int l, const int r) {
const Node v = st.query(l, r);
return r - l & 1 ? 0 : min(v.v1, v.v2[l & 1]);
};
vt<int> cost_as_L(N), cost_as_R(N);
ll tot = 0;
FOR(i, 0, N-1)
tot += (cost_as_L[i] = cost_as_R[i] = A[i] - B[i]);
vt<ll> ans(Q);
int ptr = 0, ptr2 = 0;
for (const auto &i : ord) {
for (; ptr2 < N - 2 && W[sweep2[ptr2] + 2] - W[sweep2[ptr2]] <= E[i]; ptr2++) {
const int x = sweep2[ptr2] + 1;
st.update(x, Node{A[x] - B[x], ari2{INT_MAX, INT_MAX}});
}
for (; ptr < N - 1 && W[sweep[ptr] + 1] - W[sweep[ptr]] <= E[i]; ptr++) {
const int x = sweep[ptr];
tot -= cost_as_L[L[x]];
tot -= cost_as_R[R[x+1]];
tot += (cost_as_L[L[x]] = cost_as_R[R[x+1]] = cost(L[x], R[x+1]));
assert(R[x] == x);
assert(L[x+1] == x+1);
L[R[x+1]] = L[x];
R[L[x]] = R[x+1];
}
ans[i] = tot + sum;
}
return ans;
}
