#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define double long double
vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E){
int n = W.size();
int q = E.size();
int flg = 1;
for (int x: A){
if (x != 2){
flg = 0;
}
}
for (int x: B){
if (x != 1){
flg = 0;
}
}
if (flg){
vector<long long> vec;
sort(W.begin(), W.end());
int ans = (n / 2 * 2) + 2 * (n % 2);
priority_queue<pair<int, int>> pq;
set<int> groups;
groups.insert(0);
for (int i = 0; i < n - 1; i++){
pq.push({W[i + 1] - W[i], i});
}
map<int, int> mp;
set<int> st;
st.insert(0);
mp[0] = 2 * n;
groups.insert(n);
while (!pq.empty()){
pair<int, int> p = pq.top();
pq.pop();
if ((*groups.upper_bound(p.second + 1) - *prev(groups.upper_bound(p.second + 1))) % 2 != 0){
ans--;
}
if ((*groups.upper_bound(p.second + 1) - (p.second + 1)) % 2 != 0){
ans++;
}
if ((*prev(groups.upper_bound(p.second + 1)) - (p.second + 1)) % 2 != 0){
ans++;
}
st.insert(p.first);
mp[p.first] = ans;
groups.insert(p.second + 1);
}
for (int x: E){
if (st.upper_bound(x) == st.end()){
vec.push_back((n / 2 * 2) + 2 * (n % 2));
}
else{
int y = *st.upper_bound(x);
vec.push_back(mp[y]);
}
}
return vec;
}
vector<long long> vec;
vector<pair<int, pair<int, int>>> vv(n);
for (int i = 0; i < n; i++){
vv[i].first = W[i];
vv[i].second.first = A[i];
vv[i].second.second = B[i];
}
sort(vv.begin(), vv.end());
for (int i = 0; i < n; i++){
W[i] = vv[i].first;
A[i] = vv[i].second.first;
B[i] = vv[i].second.second;
}
for (int d: E){
long long ans = 0;
for (int i = 0; i < n; i++){
ans += A[i];
}
vector<int> sep;
sep.push_back(0);
for (int i = 0; i < n - 1; i++){
if (W[i + 1] - W[i] > d){
sep.push_back(i + 1);
}
}
sep.push_back(n);
for (int i = 1; i < sep.size(); i++){
if ((sep[i] - sep[i - 1]) % 2 == 0){
for (int j = sep[i - 1]; j < sep[i]; j++){
ans -= (A[j] - B[j]);
}
}
else{
for (int j = sep[i - 1]; j < sep[i]; j++){
ans -= (A[j] - B[j]);
}
int mi = 1e9;
for (int j = sep[i - 1]; j < sep[i]; j++){
if ((j - sep[i - 1]) % 2 == 0 || (W[j + 1] - W[j - 1] <= d)){
mi = min(mi, A[j] - B[j]);
}
}
ans += mi;
}
}
vec.push_back(ans);
}
return vec;
}
/*
int main(){
vector<int> w = {1, 2, 7, 11, 14, 16};
vector<int> a = {2, 2, 2, 2, 2, 2};
vector<int> b = {1, 1, 1, 1, 1, 1};
vector<int> E = {1, 2, 3, 4, 5, 6, 7, 8};
vector<long long> ans = calculate_costs(w, a, b, E);
for (int i = 0; i < 8; i ++){
cout << ans[i] << "\n";
}
}*/
/*
____ ___ ___ ____ _____ ____ ____ ___
| | | | \ | | /| | | | \
| | | | | |____ | | | _ |____ |___/
| | | | | | | | | | | | \
|____ |___| |___/ |____ | __|__ |____| |____ | \
*/
