#include <bits/stdc++.h>
#include "nile.h"
using namespace std;
#define pb push_back
#define ll long long
struct comp{
ll sz=1,sumb,mnodd,mneven=1e18,ev=1e18,od=1e18;
};
const int MAXN=1e5+5;
int par[MAXN],first[MAXN];
comp g[MAXN];
int find(int x){
return par[x]=(par[x]==x?x:find(par[x]));
}
//. . . . . . .
ll score(int x){
x=find(x);
if(g[x].sz%2==0)return g[x].sumb;
return g[x].sumb+min(g[x].mnodd,g[x].ev);
}
void merge(int a,int b){
a=find(a);
b=find(b);
par[b]=a;
first[a]=min(first[a],first[b]);
if(g[a].sz%2){
g[a].mnodd=min(g[a].mnodd,g[b].mneven);
g[a].mneven=min(g[a].mneven,g[b].mnodd);
g[a].od=min(g[a].od,g[b].ev);
g[a].ev=min(g[a].ev,g[b].od);
}
else{
g[a].mnodd=min(g[a].mnodd,g[b].mnodd);
g[a].mneven=min(g[a].mneven,g[b].mneven);
g[a].od=min(g[a].od,g[b].od);
g[a].ev=min(g[a].ev,g[b].ev);
}
g[a].sz+=g[b].sz;
g[a].sumb+=g[b].sumb;
}
vector<long long> calculate_costs(vector<int> W,vector<int> A,vector<int> B, vector<int> E) {
pair<int,pair<int,int>> srt[W.size()];
for(int i=0;i<W.size();i++){
srt[i].first=W[i];
srt[i].second={A[i],B[i]};
}
sort(srt,srt+W.size());
for(int i=0;i<W.size();i++){
W[i]=srt[i].first;
A[i]=srt[i].second.first;
B[i]=srt[i].second.second;
}
vector<pair<int,int>> j1,j2;
for(int i=1;i<W.size();i++){
j1.pb({abs(W[i]-W[i-1]),i});
if(i>1)j2.pb({abs(W[i]-W[i-2]),i});
}
ll ans=0;
for(int i=0;i<W.size();i++){
ans+=A[i];
par[i]=i;
g[i].sumb=B[i];
g[i].mnodd=A[i]-B[i];
first[i]=i;
}
sort(j1.begin(),j1.end());
sort(j2.begin(),j2.end());
reverse(j1.begin(),j1.end());
reverse(j2.begin(),j2.end());
map<int,ll> sol;
vector<int> og=E;
sort(E.begin(),E.end());
for(int i=0;i<E.size();i++){
while(!j1.empty() && j1.back().first<=E[i]){
int idx=j1.back().second;
ans-=score(idx);
ans-=score(idx-1);
merge(idx-1,idx);
ans+=score(idx);
j1.pop_back();
}
while(!j2.empty() && j2.back().first<=E[i]){
int idx=j2.back().second;
ans-=score(idx);
int x=find(idx);
int prt=(idx-first[x])%2;
if(prt%2==1)g[x].od=min(g[x].od,(long long)A[idx-1]-B[idx-1]);
else g[x].ev=min(g[x].ev,(long long)A[idx-1]-B[idx-1]);
ans+=score(idx);
j2.pop_back();
}
sol[E[i]]=ans;
}
vector<ll> final;
for(int i=0;i<og.size();i++)final.pb(sol[og[i]]);
return final;
}
