#include "nile.h"
#include<algorithm>
#include<iostream>
#include<map>
using namespace std;
typedef long long ll;
struct DSU{
vector<int>par; // parent: -n ima root, kjer je n velikost, n ima pa non-root in to pove, da je n v isti komponenti
ll cost;
DSU(int n){
par=vector(n,-1);
cost=2*n;
}
int get(int a){
if(par[a]<0)
return a;
return par[a]=get(par[a]);
}
int merge(int a,int b){
a=get(a);
b=get(b);
if(a==b)
return 0;
if(par[a]>par[b])
swap(a,b);
cost-=get_cost(a);
cost-=get_cost(b);
par[a]+=par[b];
par[b]=a;
cost+=get_cost(a);
return 1;
}
int get_cost(int a){
int s=-par[get(a)];
if(s%2==0)
return s;
else
return s+1;
}
};
vector<ll>calculate_costs(vector<int>W,vector<int>_A,vector<int>_B,vector<int>E){
int n=(int)W.size();
sort(W.begin(),W.end());
vector<int>srt=E;
sort(srt.begin(),srt.end());
map<int,ll>ans;
vector<pair<int,int>>arr; // (W[i+1]-W[i],i)
for(int i=0;i+1<n;i++)
arr.push_back({W[i+1]-W[i],i});
sort(arr.begin(),arr.end());
reverse(arr.begin(),arr.end());
DSU dsu(n);
for(int D:srt){
while(arr.size()&&arr.back().first<=D){
dsu.merge(arr.back().second,arr.back().second+1);
arr.pop_back();
}
ans[D]=dsu.cost;
}
vector<ll>res;
for(int D:E)
res.push_back(ans[D]);
return res;
}
