#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
struct CC {
static vector<int> A, B;
static vector<i64> S;
int par, size, l, r, best;
void skip(int i) { best = min(best, A[i] - B[i]); }
i64 get_best() const { return min({best, A[l] - B[l], A[r] - B[r]}); }
i64 get_cost() const { return S[r + 1] - S[l] + (size & 1) * get_best(); }
};
vector<int> CC::A = {};
vector<int> CC::B = {};
vector<i64> CC::S = {};
struct DSU {
vector<CC> arr;
i64 cost;
int find(int u) {
if (arr[u].par == u) return u;
return arr[u].par = find(arr[u].par);
}
void join(int i) {
int u = find(i);
int v = find(i + 1);
if (u == v) return;
if (arr[u].size < arr[v].size) swap(u, v);
cost -= arr[u].get_cost();
cost -= arr[v].get_cost();
arr[u].size += arr[v].size;
arr[u].r = max(arr[u].r, arr[v].r);
arr[u].l = min(arr[u].l, arr[v].l);
arr[u].best = max(arr[u].best, arr[v].best);
arr[v].par = u;
cost += arr[u].get_cost();
}
void skip(int i) {
int u = find(i);
cost -= arr[u].get_cost();
arr[u].skip(i);
cost += arr[u].get_cost();
}
DSU(int N) : arr(N), cost(0) {
for (int i = 0; i < N; i++) {
arr[i] = {i, 1, i, i, (int)2e9};
cost += arr[i].get_cost();
}
}
};
enum EventType { JOIN, SKIP, QUERY };
struct Event {
EventType type;
int time, position;
};
bool operator<(const Event &a, const Event &b) { return tie(a.time, a.type) < tie(b.time, b.type); }
vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
vector<int> order(W.size());
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int u, int v) { return W[u] < W[v]; });
sort(W.begin(), W.end());
CC::A.resize(W.size());
CC::B.resize(W.size());
CC::S.resize(W.size() + 1);
for (int i = 0; i < W.size(); i++) {
CC::A[i] = A[order[i]];
CC::B[i] = B[order[i]];
CC::S[i + 1] = CC::S[i] + B[order[i]];
}
vector<Event> events;
for (int i = 0; i < E.size(); i++)
events.push_back({QUERY, E[i], i});
for (int i = 0; i < W.size() - 1; i++)
events.push_back({JOIN, W[i + 1] - W[i], i});
for (int i = 1; i < W.size() - 1; i++)
events.push_back({SKIP, W[i + 1] - W[i - 1], i});
DSU dsu(W.size());
vector<i64> ans(E.size());
sort(events.begin(), events.end());
for (auto [type, _, idx]: events) {
switch (type) {
case JOIN:
dsu.join(idx);
break;
case SKIP:
dsu.skip(idx);
break;
case QUERY:
ans[idx] = dsu.cost;
break;
}
}
return ans;
}
