#include <bits/stdc++.h>
#define ll long long
using namespace std;
int N, M, Q;
struct NODE
{
int parent, ranking;
int L, R;
ll min0, min1, best, sum;
}DSU[100096];
struct EDGE
{
int u, v;
ll w;
}E[200096];
inline bool comp(EDGE e1, EDGE e2) {return e1.w < e2.w;}
inline ll Get(int i)
{
if((DSU[i].R - DSU[i].L) & 1) return DSU[i].sum;
if(DSU[i].L & 1) return DSU[i].sum + min(DSU[i].best, DSU[i].min1);
return DSU[i].sum + min(DSU[i].best, DSU[i].min0);
}
inline int Find(int i)
{
while(DSU[i].parent != i) i = DSU[i].parent;
return i;
}
inline ll Union(int u, int v)
{
u = Find(u);
v = Find(v);
if(u == v) return 0;
ll RET = Get(u) + Get(v);
if(DSU[u].ranking < DSU[v].ranking) swap(u, v);
DSU[u].ranking += DSU[u].ranking == DSU[v].ranking;
DSU[v].parent = u;
DSU[u].L = min(DSU[v].L, DSU[u].L);
DSU[u].R = max(DSU[v].R, DSU[u].R);
DSU[u].min0 = min(DSU[v].min0, DSU[u].min0);
DSU[u].min1 = min(DSU[v].min1, DSU[u].min1);
DSU[u].best = min(DSU[v].best, DSU[u].best);
DSU[u].sum += DSU[v].sum;
RET -= Get(u);
return RET;
}
vector <ll> calculate_costs(vector <int> W, vector <int> A, vector <int> B, vector <int> QR)
{
N = W.size();
Q = QR.size();
vector <ll> O(Q);
vector <pair <int, int>> MO(Q), V(N);
for(int i = 0; i < Q; i++) MO[i] = {QR[i], i};
sort(MO.begin(), MO.end());
for(int i = 0; i < N; i++) V[i] = {W[i], i};
sort(V.begin(), V.end());
for(int i = 1; i < N; i++) E[++M] = {V[i - 1].second, V[i].second, V[i].first - V[i - 1].first};
for(int i = 2; i < N; i++) E[++M] = {V[i - 1].second, -1, V[i].first - V[i - 2].first};
sort(E + 1, E + M + 1, comp);
for(int i = 0; i < N; i += 2) DSU[V[i].second] = {V[i].second, 0, i, i, A[V[i].second] - B[V[i].second], 1LL << 60, 1LL << 60, B[V[i].second]};
for(int i = 1; i < N; i += 2) DSU[V[i].second] = {V[i].second, 0, i, i, 1LL << 60, A[V[i].second] - B[V[i].second], 1LL << 60, B[V[i].second]};
ll temp = 0;
for(int i = 0; i < N; i++) temp += A[i];
int i = 1;
for(pair <int, int> p : MO)
{
while((i <= M) && (E[i].w <= p.first))
{
if(E[i].v >= 0) temp -= Union(E[i].u, E[i].v);
else
{
E[i].v = Find(E[i].u);
temp -= Get(E[i].v);
DSU[E[i].v].best = min(1LL * (A[E[i].u] - B[E[i].u]), DSU[E[i].v].best);
temp += Get(E[i].v);
}
i++;
}
O[p.second] = temp;
}
return O;
}
