#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mxN = 1e5+10;
const ll INF = 1e18;
ll p[mxN], mn_odd[mxN], mn_even[mxN], mn_idx[mxN], mn_add[mxN], c[mxN];
ll ans = 0;
int get(int x) {
return p[x] < 0 ? x : p[x] = get(p[x]);
}
void uni(int a, int b) {
int a1 = a, b1 = b;
a = get(a); b = get(b);
if(a == b) {
if(b1-a1 == 2) {
ll now = c[a1+1];
if(now < mn_add[a]) {
if(-p[a] & 1) {
ll mn = mn_add[a];
if(mn_idx[a] & 1) {
mn = min(mn, mn_odd[a]);
}
else {
mn = min(mn, mn_even[a]);
}
ans -= mn;
mn_add[a] = now;
mn = mn_add[a];
if(mn_idx[a] & 1) {
mn = min(mn, mn_odd[a]);
}
else {
mn = min(mn, mn_even[a]);
}
ans += mn;
}
mn_add[a] = now;
}
}
return ;
}
if(-p[a] & 1) {
ll mn = mn_add[a];
if(mn_idx[a] & 1) {
mn = min(mn, mn_odd[a]);
}
else {
mn = min(mn, mn_even[a]);
}
ans -= mn;
}
if(-p[b] & 1) {
ll mn = mn_add[b];
if(mn_idx[b] & 1) {
mn = min(mn, mn_odd[b]);
}
else {
mn = min(mn, mn_even[b]);
}
ans -= mn;
}
p[a] += p[b];
p[b] = a;
mn_idx[a] = min(mn_idx[a], mn_idx[b]);
mn_odd[a] = min(mn_odd[a], mn_odd[b]);
mn_even[a] = min(mn_even[a], mn_even[b]);
mn_add[a] = min(mn_add[a], mn_add[b]);
if(-p[a] & 1) {
ll mn = mn_add[a];
if(mn_idx[a] & 1) {
mn = min(mn, mn_odd[a]);
}
else {
mn = min(mn, mn_even[a]);
}
ans += mn;
}
}
vector<ll> calculate_costs(vector<int> w, vector<int> a, vector<int> b, vector<int> e) {
int n = w.size(), q = e.size();
vector<array<ll, 3>> v(n);
for(int i = 0; i < n; i++) {
v[i][0] = w[i];
}
for(int i = 0; i < n; i++) {
v[i][1] = a[i];
}
for(int i = 0; i < n; i++) {
v[i][2] = b[i];
ans += b[i];
}
sort(v.begin(), v.end());
for(int i = 0; i < n; i++) {
p[i] = -1;
mn_add[i] = INF;
mn_odd[i] = INF; mn_even[i] = INF;
mn_idx[i] = i;
c[i] = v[i][1]-v[i][2];
if(i & 1) mn_odd[i] = c[i];
else mn_even[i] = c[i];
ans += c[i];
}
vector<array<ll, 3>> pairs;
for(int i = 0; i < n-1; i++) {
pairs.push_back({v[i+1][0]-v[i][0], i, i+1});
if(i+2 < n) pairs.push_back({v[i+2][0]-v[i][0], i, i+2});
}
sort(pairs.begin(), pairs.end());
int last = 0;
vector<array<int, 2>> queries;
for(int i = 0; i < q; i++) {
queries.push_back({e[i], i});
}
sort(queries.begin(), queries.end());
vector<ll> res(q);
for(int i = 0; i < q; i++) {
while(last < pairs.size() && pairs[last][0] <= queries[i][0]) {
uni(pairs[last][1], pairs[last][2]);
++last;
}
res[queries[i][1]] = ans;
}
return res;
}
/*int main()
{
//ios_base::sync_with_stdio(0);
//cin.tie(0);
vector<int> w = {15, 12, 2, 10, 21};
vector<int> a = {5, 4, 5, 6, 3};
vector<int> b = {1, 2, 2, 3, 2};
vector<int> e = {5, 9, 1};
vector<ll> real_ans = calculate_costs(w, a, b, e);
for(auto it : real_ans) {
cout << it << '\n';
}
}*/
