#include "nile.h"
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100'007
int n;
struct art
{
long long w,a,b;
} ar[MAXN];
bool cmp(art &a, art &b)
{
return a.w<b.w;
}
int par[MAXN];
int gol[MAXN];
bool vkl[MAXN];
int klkV=0;
int ft(int x)
{
if (par[x]==x) return x;
par[x]=ft(par[x]);
return par[x];
}
void dobavi(int x)
{
vkl[x]=1;
gol[x]=1;
if (x!=n-2 && vkl[x+1])
{
int y=ft(x+1);
klkV-=gol[y]/2;
gol[y]++;
par[x]=y;
klkV+=gol[y]/2;
}
if (x!=0 && vkl[x-1])
{
int y=ft(x);
int z=ft(x-1);
klkV-=gol[y]/2;
klkV-=gol[z]/2;
if (gol[y]>gol[z]) swap(y,z);
gol[z]+=gol[y];
par[y]=z;
klkV+=gol[z]/2;
}
}
vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E)
{
int Q = (int)E.size();
n=A.size();
for (int q=0;q<n;q++) ar[q]={W[q],A[q],B[q]};
sort(ar,ar+n,cmp);
vector<pair<int,int>> rzl;
for (int q=0;q<n-1;q++)
{
int df=ar[q+1].w-ar[q].w;
rzl.push_back({df,q});
}
sort(rzl.begin(),rzl.end());
vector<long long> R(Q);
vector<pair<int,int>> qu(Q);
for (int q=0;q<Q;q++)
{
qu[q].first=E[q];
qu[q].second=q;
}
sort(qu.begin(),qu.end());
for (int q=0;q<n-1;q++) par[q]=q;
for (int q=0;q<n-1;q++) vkl[q]=0;
int curd=0;
for (int curq=0;curq<Q;curq++)
{
while (curd<n-1 && rzl[curd].first<=qu[curq].first)
{
dobavi(rzl[curd].second);
curd++;
}
R[ qu[curq].second ]=2*klkV+(n-2*klkV)*2;
}
return R;
}
