#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define S second
#define F first
const int mod=1e9+7;
ll tc=0;
vector<pair<int, pair<int, int>>> h;
struct DSU
{
vector<int> ta, p, mp, im, le, mi;
DSU (int n)
{
ta.assign(n, 1); p.resize(n); im.resize(n); mp.resize(n); le.resize(n);
mi.assign(n, mod);
for(int i=0; i<n; i++)
{
p[i]=i; le[i]=i; tc+=h[i].S.F-h[i].S.S;
if(i%2==0){mp[i]=h[i].S.F-h[i].S.S; im[i]=mod;}
else{im[i]=h[i].S.F-h[i].S.S; mp[i]=mod;}
}
}
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(ta[a]<ta[b])swap(a, b);
if(ta[a]%2)
{
if(le[a]%2==0){tc-=min(mp[a], mi[a]);} else tc-=min(im[a], mi[a]);
}
if(ta[b]%2)
{
if(le[b]%2==0){tc-=min(mp[b],mi[b]);} else tc-=min(im[b],mi[b]);
}
ta[a]+=ta[b]; p[b]=a; mp[a]=min(mp[a], mp[b]); im[a]=min(im[a], im[b]);
le[a]=min(le[a], le[b]); mi[a]=min(mi[a], mi[b]);
if(ta[a]%2)
{
if(le[a]%2==0){tc+=min(mp[a], mi[a]);} else tc+=min(im[a], mi[a]);
}
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, 1); h.resize(n);
for(int i=0; i<n; i++)h[i]={w[i],{a[i], b[i]}};
sort(h.begin(), h.end()); vector<pair<pair<int, int>, pair<int, int>>> q1;
for(int i=0; i<n; i++)
{
if(i+1<n)q1.push_back({{abs(h[i].F-h[i+1].F),0}, {i, i+1}});
}
for(int i=0; i<n; i++)
{
if(i+2<n)q1.push_back({{abs(h[i].F-h[i+2].F), 1}, {i, i+2}});
}
sort(q1.begin(), q1.end());
vector<pair<int, int>> gj(q);
for(int i=0; i<q; i++){gj[i]={e[i], i};} sort(gj.begin(), gj.end());
tc=0; DSU r1(n); int rt=0;
for(int c=0; c<q; c++)
{
while(rt<q1.size()&&q1[rt].F.F<=gj[c].F)
{
if(q1[rt].S.F+1==q1[rt].S.S)r1.uni(q1[rt].S.F, q1[rt].S.S);
else
{
int ux=r1.find(q1[rt].S.F);
if(r1.ta[ux]%2)
{
if(r1.le[ux]%2==0)tc-=min(r1.mi[ux], r1.mp[ux]);
else{tc-=min(r1.mi[ux], r1.im[ux]);}
}
r1.mi[ux]=min(r1.mi[ux], h[q1[rt].S.F+1].S.F-h[q1[rt].S.F+1].S.S);
if(r1.ta[ux]%2)
{
if(r1.le[ux]%2==0)tc+=min(r1.mi[ux], r1.mp[ux]);
else{tc+=min(r1.mi[ux], r1.im[ux]);}
}
}
rt++;
}
r[gj[c].S]=tc;
}
return r;
}
