#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define S second
#define F first
const ll mod=1e18;
ll tc=0;
vector<pair<int, pair<int, int>>> h;
struct DSU
{
vector<ll> mp, im, mi0, mi, ns, qh; vector<int> p, le, lr, ta;
DSU (int n)
{
ta.assign(n, 1); p.resize(n); im.resize(n); mp.assign(n, mod); le.resize(n);
mi0.assign(n, mod); ns.resize(n); qh.resize(n); lr.resize(n); mi.resize(n);
for(int i=0; i<n; i++)
{
p[i]=i; le[i]=i; lr[i]=i; im[i]=h[i].S.F-h[i].S.S; mi[i]=h[i].S.F-h[i].S.S;
ns[i]=h[i].S.S; qh[i]=h[i].S.F; tc+=h[i].S.F;
}
}
int find(int x)
{
if(p[x]==x)return x; return p[x]=find(x);
}
bool uni(int x, int y)
{
int a=find(x), b=find(y); if(a==b)return false;
if(le[a]>le[b])swap(a, b);
tc-=qh[a]; tc-=qh[b]; ll me=mp[a], mn=im[a];
if((lr[a]-le[a]+1)%2)
{
me=min(me, im[b]); mn=min(mn, mp[b]);
}
else{me=min(me, mp[b]); mn=min(mn, im[b]);}
ll al=min({mn, mi[a], mi0[b]});
p[a]=b; ta[b]+=ta[a];
le[b]=min(le[a], le[b]); lr[b]=max(lr[a], lr[b]);
mp[b]=me; im[b]=mn; mi[b]=al;mi0[b]=min(mi0[a], mi0[b]);
ns[b]+=ns[a]; qh[b]=ns[b];
if((lr[b]-le[b]+1)%2){qh[b]+=mi[b];} tc+=qh[b];
return true;
}
};
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(); vector<long long> r(q, 0); h.resize(n);
for(int i=0; i<n; i++)h[i]={w[i],{a[i], b[i]}};
sort(h.begin(), h.end());
tc=0; DSU r1(n); vector<pair<int, int>> q1; vector<pair<int, int>> q2;
vector<pair<int, int>> gj(q);
for(int i=0; i<q; i++){gj[i]={e[i], i};} sort(gj.begin(), gj.end());
for(int i=0; i<n; i++)
{
if(i+1<n)q1.push_back({h[i+1].F-h[i].F,i});
}
sort(q1.rbegin(), q1.rend());
for(int i=0; i<n; i++)
{
if(i+2<n)q2.push_back({h[i+2].F-h[i].F, i});
}
sort(q2.rbegin(), q2.rend());
for(int c=0; c<q; c++)
{
while(!q1.empty()&&q1.back().F<=gj[c].F)
{
r1.uni(q1.back().S, q1.back().S+1); q1.pop_back();
}
while(!q2.empty()&&q2.back().F<=gj[c].F)
{
int ux=r1.find(q2.back().S), ph=h[q2.back().S+1].S.F-h[q2.back().S+1].S.S;
r1.mi[ux]=min(r1.mi[ux],(ll)ph);
tc-=r1.qh[ux];
r1.qh[ux]=r1.ns[ux]; if((r1.lr[ux]-r1.le[ux]+1)%2){r1.qh[ux]+=r1.mi[ux];}
tc+=r1.qh[ux];
r1.mi0[ux]=min(r1.mi0[ux], (ll)ph);q2.pop_back();
}
r[gj[c].S]=tc;
}
return r;
}
