#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll inf = 1e18 + 1e16;
struct SegmentTree {
struct Matrix {
vector <vector <ll>> arr;
Matrix() {
arr.resize(3);
for (int i = 0; i < 3; ++i) arr[i].resize(3, 0);
}
Matrix(ll x) {
arr.resize(3);
for (int i = 0; i < 3; ++i) arr[i].resize(3);
arr[0][0] = x;
arr[0][1] = inf;
arr[0][2] = inf;
arr[1][0] = 0;
arr[1][1] = inf;
arr[1][2] = inf;
arr[2][0] = inf;
arr[2][1] = 0;
arr[2][2] = inf;
}
};
int n;
vector <Matrix> t;
SegmentTree() = default;
SegmentTree(int n): n(n) {
t.resize(4 * n);
}
ll calc(vector <vector <ll>> &a, int i, vector <vector <ll>> &b, int j) {
return min({a[i][0] + b[0][j], a[i][1] + b[1][j], a[i][2] + b[2][j]});
}
Matrix merge(Matrix &a, Matrix &b) {
Matrix c;
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
c.arr[i][j] = calc(a.arr, i, b.arr, j);
}
}
return c;
}
void build(int v, int l, int r, vector <int> &A) {
if (r - l == 1) {
t[v] = Matrix(A[l]);
return;
}
int m = (l + r) / 2;
build(2 * v + 1, l, m, A);
build(2 * v + 2, m, r, A);
t[v] = merge(t[2 * v + 2], t[2 * v + 1]);
}
void build(vector <int> &A) {
build(0, 0, n, A);
}
void update(int v, int l, int r, int pos, int d, int x) {
if (r - l == 1) {
t[v].arr[0][d] = x;
return;
}
int m = (l + r) / 2;
if (pos < m) {
update(2 * v + 1, l, m, pos, d, x);
} else {
update(2 * v + 2, m, r, pos, d, x);
}
t[v] = merge(t[2 * v + 2], t[2 * v + 1]);
}
void update(int pos, int d, int x) {
update(0, 0, n, pos, d, x);
}
ll get() {
return t[0].arr[0][0];
}
};
struct quest {
int ind;
int d;
int t; // 0 - update1, 1 - update2, 2 - get
quest() = default;
quest(int ind, int d, int t): ind(ind), d(d), t(t) {}
bool operator<(const quest &oth) const {
return tie(d, t) < tie(oth.d, oth.t);
}
};
vector <ll> calculate_costs(vector <int> W, vector <int> A, vector <int> B, vector <int> E) {
int n = A.size();
int p[n];
iota(p, p + n, 0);
sort(p, p + n, [&](int i, int j) {
return W[i] < W[j];
});
vector <int> nW(n);
vector <int> nA(n);
vector <int> nB(n);
for (int i = 0; i < n; ++i) {
nW[i] = W[p[i]];
nA[i] = A[p[i]];
nB[i] = B[p[i]];
}
W = move(nW);
A = move(nA);
B = move(nB);
ll sm = 0;
for (int i = 0; i < n; ++i) sm += B[i];
for (int i = 0; i < n; ++i) A[i] -= B[i];
vector <quest> qs;
if (n >= 2) {
qs.push_back(quest(1, W[1] - W[0], 0));
}
for (int i = 2; i < n; ++i) {
qs.push_back(quest(i, W[i] - W[i - 2], 1));
qs.push_back(quest(i, W[i] - W[i - 1], 0));
}
int q = E.size();
vector <ll> R(q);
for (int i = 0; i < q; ++i) {
qs.push_back(quest(i, E[i], 2));
}
SegmentTree t(n);
t.build(A);
sort(qs.begin(), qs.end());
for (quest e : qs) {
if (e.t <= 1) {
t.update(e.ind, e.t + 1, e.t * A[e.ind - 1]);
} else {
R[e.ind] = t.get() + sm;
}
}
return R;
}
