#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mxN = 1e5+10;
const ll INF = 1e18;
ll ans = 0;
ll p[mxN], mn_idx[mxN], c[mxN], mn_even[mxN], mn_odd[mxN], mn_idc[mxN];
int get(int x) {
return p[x] < 0 ? x : p[x] = get(p[x]);
}
void uni(int a, int b) {
int k = abs(a-b);
a = get(a); b = get(b);
if(a == b) {
if(k == 2) {
int idx = a+1;
if(c[idx] < mn_idc[a]) {
if(-p[a] & 1) {
if(mn_idx[a] & 1) {
ans -= min(mn_idc[a], mn_odd[a]);
}
else {
ans -= min(mn_idc[a], mn_even[a]);
}
ans += c[idx];
}
mn_idc[a] = c[idx];
}
}
return ;
}
if(-p[a] & 1) {
if(mn_idx[a] & 1) {
ans -= min(mn_idc[a], mn_odd[a]);
}
else {
ans -= min(mn_idc[a], mn_even[a]);
}
}
if(-p[b] & 1) {
if(mn_idx[b] & 1) {
ans -= min(mn_idc[a], mn_odd[b]);
}
else {
ans -= min(mn_idc[a], mn_even[b]);
}
}
if(k == 2) {
int idx = a+1;
mn_idc[a] = min(mn_idc[a], c[idx]);
}
p[a] += p[b];
p[b] = a;
mn_idx[a] = min(mn_idx[a], mn_idx[b]);
mn_even[a] = min(mn_even[a], mn_even[b]);
mn_odd[a] = min(mn_odd[a], mn_odd[b]);
mn_idc[a] = min(mn_idc[a], mn_idc[b]);
if(-p[a] & 1) {
if(mn_idx[a] & 1) {
ans += min(mn_idc[a], mn_odd[a]);
}
else {
ans += min(mn_even[a], mn_idc[a]);
}
}
}
vector<ll> calculate_costs(vector<int> w, vector<int> a, vector<int> b, vector<int> e1) {
int n = w.size(), q = e1.size();
vector<array<ll, 3>> v(n);
vector<array<int, 2>> e(q);
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];
}
sort(v.begin(), v.end());
for(int i = 0; i < n; i++) {
p[i] = -1;
mn_idx[i] = i;
mn_even[i] = mn_odd[i] = INF;
mn_idc[i] = INF;
c[i] = v[i][1]-v[i][2];
if(i & 1) mn_odd[i] = c[i];
else mn_even[i] = c[i];
ans += v[i][1];
}
for(int i = 0; i < q; i++) {
e[i][0] = e1[i];
e[i][1] = i;
}
sort(e.begin(), e.end());
vector<array<ll, 3>> pairs;
for(int i = 0; i < n; 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());
vector<ll> res(q);
int last = 0;
for(int i = 0; i < q; i++) {
while(last < pairs.size() && pairs[last][0] <= e[i][0]) {
uni(pairs[last][1], pairs[last][2]);
++last;
}
res[e[i][1]] = ans;
}
return res;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
}
