#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
const int nax = 1e5+5;
long long dp[nax];
set<pair<int,int>> st;
int a[nax],b[nax];
int segtree[nax*4];
void build(int pos,int l,int r){
if(l==r){
segtree[pos]=a[l]-b[l];
return;
}
int mid=(r+l)/2;
build(pos*2+1,l,mid);
build(pos*2+2,mid+1,r);
segtree[pos]=min(segtree[pos*2+1],segtree[pos*2+2]);
}
int query(int pos,int l,int r,int left,int right){
if(l>r||r<left||l>right) return 1e9;
if(left<=l&&r<=right) return segtree[pos];
int mid=(r+l)/2;
return min(query(pos*2+1,l,mid,left,right),query(pos*2+2,mid+1,r,left,right));
}
std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A,
std::vector<int> B, std::vector<int> E) {
int n=A.size();
int q=E.size();
st.insert({0,n-1});
vector<pair<int,pair<int,int>>> tab(n);
vector<long long> answer(q);
for (int i = 0; i < n; ++i) tab[i]={W[i],{A[i],B[i]}};
sort(tab.begin(),tab.end());
st.insert({n,n});
vector<pair<int,int>> split;
long long ans=0;
for (int i = 0; i < n; ++i)
{
W[i]=tab[i].fi;
A[i]=tab[i].se.fi;
B[i]=tab[i].se.se;
ans+=B[i];
if(i) split.push_back({W[i]-W[i-1],i-1});
a[i]=A[i];
b[i]=B[i];
}
sort(split.begin(),split.end(),greater<pair<int,int>>());
vector<pair<int,int>> nabba;
for (int i = 0; i < q; ++i) nabba.push_back({E[i],i});
sort(nabba.begin(),nabba.end(),greater<pair<int,int>>());
int j=0;
build(0,0,n-1);
if(n%2) ans+=query(0,0,n-1,0,n-1);
for (int i = 0; i < q; ++i)
{
int d=nabba[i].fi;
while(j<split.size()&&split[j].fi>d){
pair<int,int> cur = *--st.upper_bound({split[j].se,n});
st.erase(cur);
if((cur.se-cur.fi+1)%2) ans-=query(0,0,n-1,cur.fi,cur.se);
if(cur.fi!=split[j].se) st.insert({cur.fi,split[j].se});
if(split[j].se+1!=cur.se) st.insert({split[j].se+1,cur.se});
if((split[j].se-cur.fi+1)%2) ans+=query(0,0,n-1,cur.fi,split[j].se);
if((cur.se-split[j].se)%2) ans+=query(0,0,n-1,split[j].se+1,cur.se);
j++;
}
answer[nabba[i].se]=ans;
}
return answer;
}
