#include <bits/stdc++.h>
#include "nile.h"
using namespace std;
vector<array<int, 2>> get_sorted_indices(const vector<int>& v);
void sort_stuff(vector<int>& w, vector<int>& a, vector<int>& b);
long long calculate_expense(const vector<int>& c, int size, int le, int skip);
void swap(int& l, int& r);
int ind_min(const vector<int>& c, int a, int b);
long long merge(vector<int>& head, vector<int>& nxt, vector<int>& tail, vector<int>& size, vector<int>& lo, vector<int>& le, vector<int>& skip, const vector<int>& c, int l, int r);
long long update_skip(const vector<int>& c, const vector<int>& head, const vector<int>& size, const vector<int>& le, vector<int>& skip, int i);
vector<long long> calculate_costs(vector<int> w, vector<int> a, vector<int> b, vector<int> e) {
sort_stuff(w, a, b);
int n = w.size();
int q = e.size();
// for (int i = 0; i < n; i++) cout << w[i] << " "; cout << "\n";
// for (int i = 0; i < n; i++) cout << a[i] << " "; cout << "\n";
// for (int i = 0; i < n; i++) cout << b[i] << " "; cout << "\n";
// for (int i = 0; i < q; i++) cout << e[i] << " " ; cout << "\n";
vector<array<int, 2>> ei = get_sorted_indices(e);
vector<array<int, 2>> intervals(n-1);
for (int i = 0; i < n - 1; i++) {
intervals[i] = {w[i+1] - w[i], i};
}
sort(intervals.begin(), intervals.end());
vector<int> c(n);
for (int i = 0; i < n; i++) c[i] = a[i] - b[i];
vector<int> head(n), nxt(n), tail(n), size(n), lo(n), le(n), skip(n);
for (int i = 0; i < n; i++) {
head[i] = i;
nxt[i] = -1;
tail[i] = i;
size[i] = 1;
lo[i] = -1;
le[i] = i;
skip[i] = -1;
}
long long cost = 0;
for (int i = 0; i < n; i++) cost += a[i];
int cnt = 0;
vector<long long> res(q);
for (auto [d, idx] : ei) {
// Merge shit
// cout << cost << " " << d << "\n";
while (cnt < n-1 && intervals[cnt][0] <= d) {
int i = intervals[cnt][1];
cost += merge(head, nxt, tail, size, lo, le, skip, c, head[i], head[i + 1]);
if (i > 0 && w[i+1] - w[i-1] <= d) {
cost += update_skip(c, head, size, le, skip, i);
}
if ((i+2) < n && w[i+2] - w[i] <= d) {
cost += update_skip(c, head, size, le, skip, i+1);
}
cnt++;
}
// cout << idx << " " << cost << "\n";
res[idx] = cost;
}
return res;
}
long long merge(vector<int>& head, vector<int>& nxt, vector<int>& tail, vector<int>& size, vector<int>& lo, vector<int>& le, vector<int>& skip, const vector<int>& c, int l, int r) {
long long change = - calculate_expense(c, size[l], le[l], skip[l]) - calculate_expense(c, size[r], le[r], skip[r]);
int new_lo, new_le, new_size, new_skip;
// Cost shit
if ((size[l] % 2) == 0) {
new_lo = ind_min(c, lo[l], lo[r]);
new_le = ind_min(c, le[l], le[r]);
}
else {
// cout << "LO: " << lo[l] << "LE: " << le[r] << "\n";
new_lo = ind_min(c, lo[l], le[r]);
new_le = ind_min(c, le[l], lo[r]);
}
new_size = size[l] + size[r];
new_skip = ind_min(c, skip[l], skip[r]);
change += calculate_expense(c, new_size, new_le, new_skip);
// cout << change << " " << l << " " << r << "\n";
// cout << "Size: " << new_size << " Skip: " << new_skip << " le: " << new_le << " lo: "<< new_lo << "\n";
if (size[r] > size[l])
swap(l, r);
nxt[tail[l]] = r;
tail[l] = tail[r];
while (r != -1) {
head[r] = l;
r = nxt[r];
}
size[l] = new_size;
skip[l] = new_skip;
lo[l] = new_lo;
le[l] = new_le;
return change;
}
long long update_skip(const vector<int>& c, const vector<int>& head, const vector<int>& size, const vector<int>& le, vector<int>& skip, int i) {
long long change = -calculate_expense(c, size[head[i]], le[head[i]], skip[head[i]]);
skip[head[i]] = ind_min(c, skip[head[i]], i);
change += calculate_expense(c, size[head[i]], le[head[i]], skip[head[i]]);
// cout << "Skip updated: " << i << " " << change << "\n";
return change;
}
long long calculate_expense(const vector<int>& c, int size, int le, int skip) {
if (size % 2 == 0)
return 0;
return c[ind_min(c, le, skip)];
}
void swap(int& l, int& r) {
int tmp = l;
l = r;
r = tmp;
}
int ind_min(const vector<int>& c, int a, int b) {
if (a == -1)
return b;
if (b == -1)
return a;
if (c[a] < c[b])
return a;
return b;
}
vector<array<int, 2>> get_sorted_indices(const vector<int>& v) {
vector<array<int, 2>> res(v.size());
for (int i = 0; i < v.size(); i++)
res[i] = {v[i], i};
sort(res.begin(), res.end());
return res;
}
void sort_stuff(vector<int>& w, vector<int>& a, vector<int>& b) {
const int n = w.size();
vector<array<int, 2>> wi = get_sorted_indices(w);
vector<int> wr(n), ar(n), br(n);
for (int i = 0; i < n; i++) {
ar[i] = a[wi[i][1]];
br[i] = b[wi[i][1]];
wr[i] = w[wi[i][1]];
}
a = ar;
b = br;
w = wr;
}
