#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
using namespace std;
int par[300005], sz[300005], res;
void make(int n){
res = 2 * n;
for(int i = 0; i < n; i++){
par[i] = i;
sz[i] = 1;
}
}
int find(int u){
if(par[u] == u) return u;
return par[u] = find(par[u]);
}
void unite(int u, int v){
u = find(u); v = find(v);
if(u == v) return;
if(sz[v] > sz[u]) swap(u, v);
if((sz[v] & 1) && (sz[u] & 1)) res -= 2;
par[v] = u;
sz[u] += sz[v];
}
vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E){
int N = W.size(), Q = E.size();
vector<ll> ans;
if(Q <= 5){
vector<tuple<int, int, int> > items;
for(int i = 0; i < N; ++i) items.push_back(make_tuple(W[i], A[i], B[i]));
sort(items.begin(), items.end());
sort(items.begin(), items.end());
for (int i = 0; i < N; ++i) {
auto [w, a, b] = items[i];
W[i] = w, A[i] = a, B[i] = b;
}
for(int i = 0; i < Q; ++i){
int d = E[i];
vector<ll> dp(N + 1, LLONG_MAX);
for(int i = 0; i < N; ++i){
if(i == 0) dp[i] = (ll)A[i];
else if(i == 1){
if(W[i] - W[i - 1] <= d) dp[i] = (ll)B[i] + (ll)B[i - 1];
else dp[i] = dp[i - 1] + (ll)A[i];
}
else{
dp[i] = dp[i - 1] + (ll)A[i];
if(W[i] - W[i - 1] <= d) dp[i] = min(dp[i], (ll)((ll)B[i] + (ll)B[i - 1] + dp[i - 2]));
if(W[i] - W[i - 2] <= d){
if(i >= 3) dp[i] = min(dp[i], (ll)((ll)B[i] + (ll)A[i - 1] + (ll)B[i - 2] + dp[i - 3]));
else dp[i] = min(dp[i], (ll)((ll)B[i] + (ll)A[i - 1] + (ll)B[i - 2]));
}
}
}
ans.push_back(dp[N - 1]);
}
}else{
vector<pair<ll, ll> > v;
vector<pair<ll, pair<int, int> > > vv;
for(int i = 0; i < N; i++) v.push_back({W[i], i});
sort(v.begin(), v.end());
for(int i = 1; i < N; i++) vv.push_back({v[i].ff - v[i - 1].ff, {v[i - 1].ss, v[i].ss}});
sort(vv.begin(), vv.end());
vector<pair<int, int> > e;
for(int i = 0; i < Q; i++) e.push_back({E[i], i});
sort(e.begin(), e.end());
int idx = 0;
for(int q = 0; q < Q; q++){
int d = e[q].ff, num = e[q].ss;
while(vv[idx].ff <= d && idx < vv.size()){
int u = vv[idx].ss.ff, v = vv[idx].ss.ss;
unite(u, v);
idx++;
}
ans[num] = res;
}
}
return ans;
}
