#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vll vector<ll>
#define vvll vector<vll>
#define pll pair<ll, ll>
#define pill pair<ll, pll>
#define vpll vector<pll>
const ll INF = 1e17;
struct DSU {
ll n, totalcost = 0;
//id = comp, size = size, evenpot = min cost of element on even position, odd same (where can )
//
vll id, size, anyevenopt, anyoddopt, skipeven, skipodd, cost, mn, C;
DSU(vll& _C) {
n = _C.size();
for (int i = 0; i < n; i++) {
C.push_back(_C[i]);
id.push_back(i);
size.push_back(1);
anyevenopt.push_back(i&1 ? INF : _C[i]);
anyoddopt.push_back(i&1 ? _C[i] : INF);
skipeven.push_back(INF);
skipodd.push_back(INF);
cost.push_back(_C[i]);
totalcost += _C[i];
mn.push_back(i);
}
}
ll find(int x) {return x==id[x] ? x : id[x] = find(id[x]);}
void unite_consecutive(int a, int b) {
//here we are joining i, i+1
a = find(a); b = find(b);
if (size[a] < size[b]) swap(a, b);
//if part of same component -> ignore I guess??
if (a==b) return;
//now we need to join the information
ll newsize = size[a] + size[b];
ll newaeopt = min(anyevenopt[a], anyevenopt[b]), newaopt = min(anyoddopt[a], anyoddopt[b]);
ll newskipeven = min(skipeven[a], skipeven[b]), newskipodd = min(skipodd[a], skipodd[b]);
ll newmn = min(mn[a], mn[b]);
ll newcost = INF;
if (newsize&1) {
//skip any same parity (even, skip, even) or skip skip other parity (odd, skip, odd) with (_,_)
if (newmn&1) newcost = min({newcost, newaopt, newskipeven});
else newcost = min({newcost, newaeopt, newskipodd});
} else newcost = 0;
//now join all info together
totalcost = totalcost - cost[a] - cost[b] + newcost;
id[b] = a; size[a] = newsize; anyevenopt[a] = newaeopt; anyoddopt[a] = newaopt; skipeven[a] = newskipeven; skipodd[a] = newskipodd;
cost[a] = newcost; mn[a] = newmn;
}
void unite_skip(int i) {
//i will be in a specific component a
int a = find(i);
//we just have to update the skip vals
if (i&1) {
//we update odd skip (i is already included in anyskip)
skipodd[a] = min(skipodd[a], C[i]);
} else skipeven[a] = min(skipeven[a], C[i]);
if (size[a]&1) {
//update the cost
if ((i-mn[a])%2) {
ll newcost = (i&1 ? min(cost[a], skipodd[a]) : min(cost[a], skipeven[a]));
totalcost = totalcost - cost[a] + newcost;
cost[a] = newcost;
}
}
}
};
vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
reverse(A.begin(), A.end()); reverse(W.begin(), W.end()); reverse(B.begin(), B.end());
int n = A.size(), q = E.size();
vll C(n, 0), res(q, 0);
ll basecost = accumulate(B.begin(), B.end(), 0LL);
for (int i = 0; i < n; i++) C[i] = A[i] - B[i];
priority_queue<pill, vector<pill>, greater<pill>> events;
//here all indicies are sorted by Weight
vll indices(n);
iota(indices.begin(), indices.end(), 0);
sort(indices.begin(), indices.end(), [&](int i, int j) {return W[i] < W[j];});
for (int i = 0; i < n-1; i++) events.push({abs(W[indices[i]] - W[indices[i+1]]), {0, i}});
for (int i = 1; i < n-1; i++) events.push({abs(W[indices[i+1]] - W[indices[i-1]]), {1, i}});
for (int i = 0; i < q; i++) events.push({E[i], {2, i}});
vll _C;
for (int i : indices) _C.push_back(C[i]);
DSU uf(_C);
while (!events.empty()) {
auto p = events.top();
events.pop();
if (p.second.first==2) {
//process query;
res[p.second.second] = uf.totalcost+basecost;
} else if (p.second.first==0) {
//joining two consecutive things
int a = p.second.second, b = p.second.second+1;
uf.unite_consecutive(a, b);
} else {
//joining 2 seperate
int i = p.second.second;
uf.unite_skip(i);
}
}
return res;
}
