#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N=2e5+1;
int c[N],n,v[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);
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[x].val)%2==1)
{
ans+=min(arb[x].best_impar,arb[x].best_alb);
}
}
long long rasp[N];
vector<long long> calculate_costs(vector<int> W,vector<int>A,vector<int>B,vector<int>E)
{
n=W.size();
for(int i=1; i<=n; i++)
{
v[i]=W[i-1];
ax[i]=A[i-1];
bx[i]=B[i-1];
ans+=ax[i];
cx[i]=ax[i]-bx[i];
}
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=cx[i];
}
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]-v[i]});
if(i+2<=n)
muchii.push_back({i,i+2,v[i+2]-v[i]});
}
sort(muchii.begin(),muchii.end(),[](muchie x,muchie y)
{
return x.c<y.c;
});
int pointer=0;
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,cx[a+1]);
if(abs(arb[d].val)%2==1)
ans+=min(arb[d].best_impar,arb[d].best_alb);
}
}
rasp[qr[i].ind]=ans;
}
vector<long long>buffer;
for(int i=1;i<=q;i++)
buffer.push_back(rasp[i]);
return buffer;
}
