#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
#define DEBUG(x) do { std::cerr << x; } while (0)
struct DSU {
vector<int> f;
DSU(int n) {
f = vector<int>(n, 0);
for(int i = 0; i < n; i++) {
f[i] = i;
}
}
// Only path copmression already log n
int find(int i) {
if(f[i] == i) {
return i;
}
return f[i] = find(f[i]);
}
};
template<class T>
bool cmin(T& a, T b) {
if(a > b) {
a = b;
return true;
}
return false;
}
const int INF = 1e9 + 10;
typedef long long ll;
std::vector<ll> calculate_costs(std::vector<int> W, std::vector<int> A,
std::vector<int> B, std::vector<int> E) {
int Q = (int)E.size();
int n = W.size();
ll sumA = 0;
vector<pair<int, int>> data;
unordered_map<int, vector<int>> D;
for(int i = 0; i < n; i++) {
sumA += A[i];
D[W[i]].push_back(A[i] - B[i]);
// printf("W[i] = %d D[i] = %d\n", W[i], A[i]-B[i]);
}
sort(begin(W), end(W));
W.resize(unique(begin(W), end(W)) - begin(W));
// for(int i = 0; i < W.size(); i++) { printf("%d ", W[i]); } puts("");
DSU dsu(W.size());
vector<int> wcnt(W.size(), 0);
vector<ll> wsum(W.size(), 0);
vector<ll> wcon(W.size(), 0);
vector<int> wpre(W.size(), 0);
vector<int> wmin(W.size(), 0);
vector<pair<int, int>> wlow(W.size(), {0, 0});
ll sumD = 0;
for(int i = 0; i < W.size(); i++) {
wmin[i] = INF;
for(auto d: D[W[i]]) {
wcnt[i]++;
wsum[i] += d;
cmin(wmin[i], d);
}
wpre[i] = wcnt[i] + (i > 0 ? wpre[i - 1] : 0);
if(wcnt[i] == 1) {
wlow[i] = {wmin[i], INF};
} else {
wlow[i] = {wmin[i], wmin[i]};
}
wcon[i] = wsum[i];
// Sacrifice
if(wcnt[i] % 2 == 1) {
wcon[i] -= wlow[i].first;
}
sumD += wcon[i];
}
vector<pair<int, int>> P;
for(int i = 1; i < W.size(); i++) {
P.push_back({W[i] - W[i - 1], i});
if(i > 1) P.push_back({W[i] - W[i - 2], -i});
}
sort(begin(P), end(P));
vector<int> QI;
for(int i = 0; i < Q; i++) QI.push_back(i);
sort(begin(QI), end(QI), [&](int i, int j) { return E[i] < E[j]; });
std::vector<long long> R(Q, 0);
int pi = 0;
for(int qi: QI) {
int e = E[qi];
// printf("qi=%d e=%d \n", qi, e);
// Expand
while(pi < P.size() && P[pi].first <= e) {
int wi = abs(P[pi].second);
int delta = P[pi].second < 0 ? 2 : 1;
int l, r;
// We know these are connected already, just
if(delta == 2) {
// printf("delta = %d, [%d, %d]\n", delta, wi-2, wi);
l = dsu.find(wi);
// Reset
sumD -= wcon[l];
int pre = wpre[wi - 2] - (l > 0 ? wpre[l - 1] : 0);
// Need to check against raw size
if(D[W[wi - 1]].size() == 1) {
if(pre % 2 == 0) {
cmin(wlow[l].second, wmin[wi - 1]);
} else {
cmin(wlow[l].first, wmin[wi - 1]);
}
} else {
cmin(wlow[l].first, wmin[wi - 1]);
cmin(wlow[l].second, wmin[wi - 1]);
}
} else { // Here we connect them together
l = dsu.find(wi-1);
r = dsu.find(wi);
// Reset
sumD -= wcon[l];
sumD -= wcon[r];
wsum[l] += wsum[r];
int lcnt = wcnt[l];
int rcnt = wcnt[r];
if(lcnt % 2 == 0) {
cmin(wlow[l].first, wlow[r].first);
cmin(wlow[l].second, wlow[r].second);
} else {
cmin(wlow[l].first, wlow[r].second);
cmin(wlow[l].second, wlow[r].first);
}
wcnt[l] = lcnt + rcnt;
dsu.f[r] = l;
}
if(wcnt[l] % 2 == 0) {
wcon[l] = wsum[l];
} else {
wcon[l] = wsum[l] - wlow[l].first;
}
sumD += wcon[l];
// printf("l = %d wcnt = %d low = [%d, %d] con=%d\n", l, wcnt[l], wlow[l].first, wlow[l].second, wcon[l]);
// END
pi++;
}
// printf("sumA=%d sumD=%d\n", sumA, sumD);
R[qi] = sumA - sumD;
}
return R;
}
