#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N=2e5+1;
int c[N],n,q;
int ax[N],bx[N],cx[N];
struct query
{
int ind,val;
} qr[N];
struct dsu
{
int val,best_par,best_impar,best_alb;
} arb[N];
struct muchie
{
int a,b,c;
};
int get(int x)
{
int nod1=x;
while(arb[nod1].val>0)
{
nod1=arb[nod1].val;
}
while(arb[x].val>0)
{
int mid=arb[x].val;
arb[x].val=nod1;
x=mid;
}
return x;
}
long long ans=0;
void merge(int x,int y)
{
x=get(x),y=get(y);
//cout<<x<<" "<<y<<" "<<"deci"<<" "<<arb[x].val<<" "<<arb[y].val<<'\n';
int best_par=arb[x].best_par;
int best_impar=arb[x].best_impar;
int best_alb=arb[x].best_alb;
if(abs(arb[x].val)%2==1)
{
ans-=min(best_impar,best_alb);
}
if(abs(arb[y].val)%2==1)
{
ans-=min(arb[y].best_impar,arb[y].best_alb);
}
if(abs(arb[x].val)%2==0)
{
best_par=min(arb[y].best_par,best_par);
best_impar=min(arb[y].best_impar,best_impar);
best_alb=min(arb[y].best_alb,best_alb);
}
else
{
best_par=min(best_par,arb[y].best_impar);
best_impar=min(best_impar,arb[y].best_par);
best_alb=min(best_alb,arb[y].best_alb);
}
if(arb[x].val<arb[y].val)
{
arb[x].val+=arb[y].val;
arb[y].val=x;
arb[x].best_par=best_par;
arb[x].best_impar=best_impar;
arb[x].best_alb=best_alb;
}
else
{
arb[y].val+=arb[x].val;
arb[x].val=y;
arb[y].best_par=best_par;
arb[y].best_impar=best_impar;
arb[y].best_alb=best_alb;
}
if(abs(arb[get(x)].val)%2==1)
{
ans+=min(arb[get(x)].best_impar,arb[get(x)].best_alb);
}
}
struct schi
{
int w,a,b,c;
} v[N];
long long rasp[N];
vector<long long> calculate_costs(vector<int> W,vector<int>A,vector<int>B,vector<int>E)
{
n=W.size();
vector<long long>buffer;
for(int i=1; i<=n; i++)
{
v[i].w=W[i-1];
v[i].a=A[i-1];
v[i].b=B[i-1];
v[i].c=v[i].a-v[i].b;
ans+=v[i].a;
}
sort(v+1,v+n+1,[](schi x,schi y){return x.w<y.w;});
for(int i=1; i<=n; i++)
{
arb[i].val=-1;
arb[i].best_par=1e9+1;
arb[i].best_alb=1e9+1;
arb[i].best_impar=v[i].c;
}
q=E.size();
for(int i=1; i<=q; i++)
{
qr[i].ind=i;
qr[i].val=E[i-1];
}
sort(qr+1,qr+q+1,[](query x,query y)
{
return x.val<y.val;
});
vector<muchie>muchii;
for(int i=1; i<n; i++)
{
if(i+1<=n)
muchii.push_back({i,i+1,v[i+1].w-v[i].w});
if(i+2<=n)
muchii.push_back({i,i+2,v[i+2].w-v[i].w});
}
sort(muchii.begin(),muchii.end(),[](muchie x,muchie y)
{
return x.c<y.c;
});
int pointer=0;
/*for(int i=1;i<=n;i++)
{
cout<<v[i].w<<" ";
}
cout<<'\n';
for(int i=0;i<muchii.size();i++)
{
cout<<muchii[i].a<<" "<<muchii[i].b<<" "<<muchii[i].c<<'\n';
}*/
for(int i=1; i<=q; i++)
{
while(pointer<muchii.size()&&muchii[pointer].c<=qr[i].val)
{
int a=muchii[pointer].a;
int b=muchii[pointer].b;
if(b-a==1)
merge(a,b);
else
{
int d=get(a);
if(abs(arb[d].val)%2==1)
{
ans-=min(arb[d].best_impar,arb[d].best_alb);
}
arb[d].best_alb=min(arb[d].best_alb,v[a+1].c);
if(abs(arb[d].val)%2==1)
ans+=min(arb[d].best_impar,arb[d].best_alb);
}
pointer++;
}
rasp[qr[i].ind]=ans;
}
//merge(2,3);
for(int i=1; i<=q; i++)
buffer.push_back(rasp[i]);
return buffer;
}
