#include "bits/stdc++.h"
using namespace std;
#ifdef duc_debug
#include "bits/debug.h"
#else
#include "nile.h"
#define debug(...)
#endif
const int maxn = 1e5 + 5;
const int inf = 1e9;
int n, q;
long long ans;
struct info {
int w, a, b;
} a[maxn];
pair<int, int> que[maxn];
struct dsu {
int n;
vector<int> left_most;
vector<int> lab;
vector<int> odd;
vector<int> even;
vector<int> temp_even, temp_odd;
void resize(int &sz) {
left_most.resize(sz + 1);
even.resize(sz + 1);
odd.resize(sz + 1);
temp_even.resize(sz + 1);
temp_odd.resize(sz + 1);
}
dsu() {}
dsu(int n) : n(n), lab(n + 1, -1) {
resize(n);
for(int i = 1; i <= n; ++i) {
left_most[i] = i;
even[i] = inf;
temp_even[i] = temp_odd[i] = inf;
odd[i] = a[i].a - a[i].b;
}
}
int find(int u) {
return lab[u] < 0 ? u : lab[u] = find(lab[u]);
}
void refine(int u, int v) {
if(left_most[u] < left_most[v]) {
if(lab[u] & 1) {
swap(odd[v], even[v]);
swap(temp_odd[v], temp_even[v]);
}
}
else {
if(lab[v] & 1) {
swap(odd[u], even[u]);
swap(temp_odd[u], temp_even[u]);
}
}
}
void join(int u, int v) {
u = find(u), v = find(v);
if(u == v) return;
if(lab[u] > lab[v]) swap(u, v);
if(lab[u] & 1) {
ans -= min(odd[u], temp_even[u]);
}
if(lab[v] & 1) {
ans -= min(odd[v], temp_even[v]);
}
refine(u, v);
even[u] = min(even[u], even[v]);
odd[u] = min(odd[u], odd[v]);
left_most[u] = min(left_most[u], left_most[v]);
temp_odd[u] = min(temp_odd[u], temp_odd[v]);
temp_even[u] = min(temp_even[u], temp_even[v]);
lab[u] += lab[v];
lab[v] = u;
if(lab[u] & 1) {
ans += min(odd[u], temp_even[u]);
}
}
void make(int u) {
int val = a[u].a - a[u].b;
int root = find(u);
if((u - left_most[root] + 1) & 1) {
temp_odd[root] = min(temp_odd[root], val);
}
else {
if(lab[root] & 1) {
ans -= min(odd[root], temp_even[root]);
}
temp_even[root] = min(temp_even[root], val);
if(lab[root] & 1) {
ans += min(odd[root], temp_even[root]);
}
}
}
} d;
vector<long long> solve() {
for(int i = 1; i <= n; ++i) {
ans += a[i].a;
}
sort(que + 1, que + q + 1);
sort(a + 1, a + n + 1, [](const info &x, const info &y) -> bool {
return x.w < y.w;
});
vector<pair<int, int>> diff;
vector<pair<int, int>> diff_mid;
for(int i = 2; i <= n; ++i) {
diff.push_back(make_pair(a[i].w - a[i - 1].w, i));
if(i < n) {
diff_mid.push_back(make_pair(a[i + 1].w - a[i - 1].w, i));
}
}
debug(ans);
sort(diff.begin(), diff.end(), greater<pair<int, int>>());
sort(diff_mid.begin(), diff_mid.end(), greater<pair<int, int>> ());
d = dsu(n);
vector<long long> res(q);
for(int i = 1; i <= q; ++i) {
while(!diff.empty() and diff.back().first <= que[i].first) {
d.join(diff.back().second - 1, diff.back().second);
diff.pop_back();
}
while(!diff_mid.empty() and diff_mid.back().first <= que[i].first) {
d.make(diff_mid.back().second);
diff_mid.pop_back();
}
res[que[i].second - 1] = ans;
}
// for(int i = 0; i < q; ++i) {
// cout << res[i] << '\n';
// }
return res;
}
vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
n = (int)W.size();
for(int i = 0; i < n; ++i) {
a[i + 1].w = W[i];
a[i + 1].a = A[i];
a[i + 1].b = B[i];
}
q = (int)E.size();
for(int i = 0; i < q; ++i) {
que[i + 1] = make_pair(E[i], i + 1);
}
return solve();
}
