#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
const int N = 1e5 + 5;
int n;
int root[N], odd_mn[N], even_mn[N], lf[N], best_mid[N], sz[N];
int f(int x) {
if(x == root[x]) {
return x;
}
return root[x] = f(root[x]);
}
vector<ll> calculate_costs(vector<int> w, vector<int> a, vector<int> b, vector<int> qd) {
int q = (int) qd.size();
n = (int) a.size();
vector<int> ord(n);
for(int i = 0; i < n; i++) {
ord[i] = i;
}
sort(ord.begin(), ord.end(), [&](int i, int j){
return w[i] < w[j];
});
vector<ii> dists;
for(int i = 1; i < n; i++) {
dists.push_back({w[ord[i]] - w[ord[i - 1]], i});
}
sort(dists.begin(), dists.end());
reverse(dists.begin(), dists.end());
vector<ii> mids;
for(int i = 1; i + 1 < n; i++) {
mids.push_back({w[ord[i + 1]] - w[ord[i - 1]], i});
}
sort(mids.begin(), mids.end());
reverse(mids.begin(), mids.end());
ll add = 0;
for(int i = 0; i < n; i++) {
a[i] -= b[i];
add += b[i];
}
ll ans = add;
for(int i = 0; i < n; i++) {
root[i] = i;
odd_mn[i] = even_mn[i] = 1e9;
if(i % 2 == 0) {
even_mn[i] = a[ord[i]];
}
else {
odd_mn[i] = a[ord[i]];
}
lf[i] = i;
sz[i] = 1;
best_mid[i] = (int) 1e9;
ans += a[ord[i]];
}
vector<int> q_ord(q);
for(int i = 0; i < q; i++) {
q_ord[i] = i;
}
sort(q_ord.begin(), q_ord.end(), [&](int i, int j){
return qd[i] < qd[j];
});
vector<ll> ret(q, 0);
auto cost = [&](int x){
if(sz[x] % 2 == 0) {
return 0;
}
int res = 1e9;
if(lf[x] % 2 == 0) {
res = even_mn[x];
}
else {
res = odd_mn[x];
}
res = min(res, best_mid[x]);
return res;
};
auto merge = [&](int x, int y){
root[y] = x;
sz[x] += sz[y];
even_mn[x] = min(even_mn[x], even_mn[y]);
odd_mn[x] = min(odd_mn[x], odd_mn[y]);
best_mid[x] = min(best_mid[x], best_mid[y]);
};
for(int it = 0; it < q; it++) {
int d = qd[q_ord[it]];
while((int) dists.size() and dists.back().first <= d) {
// puts("work");
int i = dists.back().second;
dists.pop_back();
int x = f(i - 1);
int y = f(i);
ans -= cost(x);
ans -= cost(y);
merge(x, y);
ans += cost(x);
}
while((int) mids.size() and mids.back().first <= d) {
int i = mids.back().second;
mids.pop_back();
int x = f(i);
ans -= cost(x);
best_mid[x] = min(best_mid[x], a[ord[i]]);
ans += cost(x);
}
// printf("ans = %lld\n", ans);
ret[q_ord[it]] = ans;
}
return ret;
}
