#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define pii pair <int, int>
#define emb emplace_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define iShowSpeed cin.tie(NULL)->sync_with_stdio(false)
#define pvi pair <vector <int32_t>, int>
const int N = 1e5 + 5;
const int inf = 1e18;
int n, w[N], a[N], b[N], alone[N], idx[N], pref[N], sum;
vector <int> idxB, idB;
vector <pii> artifacts(1);
vector <int> artifactsB, Aprices;
struct {
int seg[4 * N];
void build(int l, int r, int i){
if (l == r) return seg[i] = a[l], void();
int mid = (l + r) / 2;
build(l, mid, 2 * i), build(mid + 1, r, 2 * i + 1);
seg[i] = min(seg[2 * i], seg[2 * i + 1]);
}
int query(int l, int r, int i, int ll, int rr){
if (l >= ll && r <= rr) return seg[i];
else return inf;
int mid = (l + r) / 2;
return min(query(l, mid, 2 * i, ll, rr), query(mid + 1, r, 2 * i + 1, ll, rr));
}
} segA;
struct {
int seg[4 * N];
void build(int l, int r, int i){
if (l == r) return seg[i] = b[l], void();
int mid = (l + r) / 2;
build(l, mid, 2 * i), build(mid + 1, r, 2 * i + 1);
seg[i] = min(seg[2 * i], seg[2 * i + 1]);
}
int query(int l, int r, int i, int ll, int rr){
if (l >= ll && r <= rr) return seg[i];
else return inf;
int mid = (l + r) / 2;
return min(query(l, mid, 2 * i, ll, rr), query(mid + 1, r, 2 * i + 1, ll, rr));
}
} segB;
int solve(int d){
// cout << "D is " << d << "\n";
// int sz = idxB.size();
vector <int> left(n + 1), right(n + 1), mx(n + 1);
int j = 0;
for (auto i : idxB) {
int w = artifactsB[j++];
int l = lower_bound(artifactsB.begin(), artifactsB.end(), w - d) - artifactsB.begin();
int r = upper_bound(artifactsB.begin(), artifactsB.end(), w + d) - artifactsB.begin() - 1;
left[i] = l;
right[i] = r;
}
j = 0;
vector <pii> intervals;
for (auto i : idxB) {
// int ii = artifacts[i].second;
// cout << i << ": idx is " << ii << ": weight is " << artifactsB[j++] << ": bounds are " << left[i] << ", " << right[i] << ": there are " << right[i] - left[i] + 1 << " in the range" << "\n";
if (intervals.empty() || left[i] > intervals.back().second) intervals.emb(left[i], right[i]);
else intervals.back().second = max(intervals.back().second, right[i]);
}
int ans = sum;
for (auto [l, r] : intervals) {
// cout << "[" << l << ", " << r << "]\n";
if ((r - l + 1) % 2 == 0) continue;
int cur = inf;
for (int i = l; i <= r; i++) {
if (i == l || i == r) cur = min(cur, Aprices[i]);
if (right[i - 1] == i && left[i + 1] == i) continue;
cur = min(cur, Aprices[i]);
}
ans += cur;
}
// cout << "--------------------------------------------------------------\n";
return ans;
}
vector <int> calculate_costs(vector<int32_t> ww, vector<int32_t> aa, vector<int32_t> bb, vector<int32_t> e) {
n = ww.size();
// int32_t q = (int32_t)e.size();
for (int32_t i = 0; i < n; i++) {
int mn = min(aa[i], bb[i]);
sum += mn;
w[i + 1] = ww[i];
a[i + 1] = aa[i] - mn;
b[i + 1] = bb[i] - mn;
if (a[i + 1] == 0) a[i + 1] = inf;
if (b[i + 1] == 0) b[i + 1] = inf;
if (a[i + 1] == inf) alone[i + 1] = 1;
artifacts.emb(ww[i], i + 1);
}
sort(all(artifacts));
for (int i = 1; i <= n; i++) {
idx[i] = artifacts[i].second;
if (!alone[idx[i]]) idxB.emb(i), artifactsB.emb(artifacts[i].first), Aprices.emb(a[idx[i]]);
}
segA.build(1, n, 1);
segB.build(1, n, 1);
for (auto e : idxB) pref[e]++;
for (int i = 1; i <= n; i++) pref[i] += pref[i - 1];
vector <int> r;
for (auto i : e) {
r.emb(solve(i));
}
return r;
}
