#include <bits/stdc++.h>
#include "nile.h"
// #include "grader.cpp"
using namespace std;
#define ll long long
#define sz(s) (int)s.size()
#define ff first
#define ss second
ll sp[5][200005][30];
vector <vector <ll>> st;
ll f(int x, int y, bool z){
int lg1 = log2(y-x+1);
return min(sp[z][x][lg1],sp[z][y-(1LL<<lg1)+1][lg1]);
}
ll upd(int nd, int l, int r, int ind, bool z, ll vl){
if(l > ind or r < ind) return st[z][nd];
if(l == r) return st[z][nd] = vl;
int md = (l + r) / 2;
return st[z][nd] = min(upd(nd*2,l,md,ind,z,vl), upd(nd*2+1,md+1,r,ind,z,vl));
}
ll fnd(int nd, int l, int r, int x, int y, bool z){
if(l > y or r < x) return 1e18;
if(l >= x and r <= y) return st[z][nd];
int md = (l + r) / 2;
return min(fnd(nd*2,l,md,x,y,z), fnd(nd*2+1,md+1,r,x,y,z));
}
vector<ll> calculate_costs(vector<int> w, vector<int> a, vector<int> b, vector<int> e){
int q = sz(e), n = sz(a);
vector <int> e1 = e;
vector <ll> vans;
sort(e.begin(), e.end());
ll d = e[0];
vector <pair<ll,pair<ll,ll>>> v;
for(int i = 0; i < n; i++){
v.push_back({w[i],{a[i],b[i]}});
}
map <pair<int,int>, ll> m;
map <int,int> m1;
sort(v.begin(), v.end());
ll ans = 0;
bool tr = 0;
set <int> s;
vector <pair<ll,int>> dis, dis1;
for(int i = 0; i < n-1; i++){
int ind = i;
while(ind < (n-1)){
if(v[ind+1].ff - v[ind].ff > d) break;
ind++;
}
ll k = 0;
for(int j = i; j <= ind; j++){
k += (v[j].ss.ss);
}
ll k2 = k;
k = 1e18;
if((ind-i) % 2 == 1){
k = k2;
}
else {
for(int j = i; j <= ind; j++){
ll k1 = k2;
k1 -= (v[j].ss.ss);
k1 += (v[j].ss.ff);
if((j-i) % 2 == 0){
k = min(k, k1);
}
else {
if(v[j+1].ff-v[j-1].ff <= d){
k = min(k, k1);
}
}
}
k = min(k, k2 + (v[i].ss.ff-v[i].ss.ss));
k = min(k, k2 + (v[ind].ss.ff-v[ind].ss.ss));
}
if(ind != n-1){
dis.push_back({v[ind+1].ff-v[ind].ff,ind});
}
m[{i,ind}] = k;
s.insert(ind);
m1[i] = ind;
m1[ind] = i;
i = ind;
ans += k;
if(i == n-1) tr = 1;
}
if(tr == 0){
ans += v[n-1].ss.ff;
m[{n-1,n-1}] = v[n-1].ss.ff;
m1[n-1] = n-1;
s.insert(n-1);
}
sort(dis.rbegin(), dis.rend());
vector <ll> v1, p(n,0);
p[0] = v[0].ss.ss;
for(int i = 1; i < n; i++){
p[i] = p[i-1] + v[i].ss.ss;
}
for(int i = 0; i < 2; i++){
for(int j = 0; j < n; j++){
for(int i1 = 0; i1 < 27; i1++){
sp[i][j][i1] = 1e18;
}
}
}
for(int i = 0; i < n; i++){
sp[i%2][i][0] = (v[i].ss.ff-v[i].ss.ss);
}
for(int j = 1; j < 27; j++){
for(int i = 0; i < n-(1LL<<j)+1; i++){
sp[0][i][j] = min(sp[0][i][j-1],sp[0][i+(1LL<<(j-1))][j-1]);
sp[1][i][j] = min(sp[1][i][j-1],sp[1][i+(1LL<<(j-1))][j-1]);
}
}
for(int i = 1; i < n-1; i++){
dis1.push_back({(v[i+1].ff-v[i-1].ff),i});
}
sort(dis1.rbegin(), dis1.rend());
st.assign(3, vector <ll> (n*8,1e18));
map <ll,ll> mp;
mp[d] = ans;
for(int i = 1; i < q; i++){
d = e[i];
while(sz(dis1) > 0){
if(d >= dis1.back().ff){
int x = dis1.back().ss;
dis1.pop_back();
upd(1,0,n-1,x,x%2,(v[x].ss.ff-v[x].ss.ss));
int y = *s.lower_bound(x);
int y1 = m1[y];
ll z1 = ((y1 != y and (y-y1+1) % 2 == 1) ? fnd(1,0,n-1,y1+1,y-1,1-(y1%2)) : 1e18), z2 = p[y];
if(y1 != 0) z2 -= p[y1-1];
if(z1+z2 < m[{y1,y}]){
ans -= m[{y1,y}];
ans += (z1+z2);
m[{y1,y}] = (z1+z2);
}
}
else break;
}
while(sz(dis) > 0){
if(d >= dis.back().ff){
int x = dis.back().ss;
dis.pop_back();
s.erase(s.find(x));
ans -= m[{m1[x],x}];
ans -= m[{x+1,m1[x+1]}];
int a1 = m1[x], b1 = m1[x+1];
m1[a1] = b1;
m1[b1] = a1;
ll y = p[b1];
if(a1 > 0) y -= p[a1-1];
if((b1-a1) % 2 == 1){
m[{a1,b1}] = y;
}
else {
ll a2 = (f(a1,b1,(a1%2)));
if(a1 != b1) a2 = min(a2,fnd(1,0,n-1,a1+1,b1-1,1-(a1%2)));
y += a2;
m[{a1,b1}] = y;
}
ans += y;
}
else break;
}
mp[d] = ans;
}
for(auto i : e1){
vans.push_back(mp[i]);
}
return vans;
}
