#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define pii pair <int, int>
#define tiii tuple <int, int, int>
#define emb emplace_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define iShowSpeed cin.tie(NULL)->sync_with_stdio(false)
#define pvi pair <vector <int32_t>, int>
const int N = 1e5 + 5;
const int inf = 1e18;
int n, w[N], a[N], b[N], alone[N], idx[N], pref[N], sum;
vector <int> idxB, idB;
vector <pii> artifacts(1);
vector <int> artifactsB, Aprices;
int lb[N], rb[N], sz[N], oddmin[N], evenmin[N], specialmin[N], par[N], mn;
int dsu(int aa){
return par[aa] = (aa == par[aa] ? aa : dsu(par[aa]));
}
int parity(int node){
if (sz[node] % 2 == 0) return 0;
if (lb[node] % 2) return min(specialmin[node], oddmin[node]);
else return min(specialmin[node], evenmin[node]);
}
void unite(int u, int v){
if (dsu(u) == dsu(v)) return;
mn -= (parity(dsu(u)) + parity(dsu(v)));
lb[dsu(v)] = min(lb[dsu(v)], lb[dsu(u)]);
rb[dsu(v)] = min(rb[dsu(v)], rb[dsu(u)]);
sz[dsu(v)] += sz[dsu(u)];
oddmin[dsu(v)] = min(oddmin[dsu(v)], oddmin[dsu(u)]);
evenmin[dsu(v)] = min(evenmin[dsu(v)], evenmin[dsu(u)]);
specialmin[dsu(v)] = min(specialmin[dsu(v)], specialmin[dsu(u)]);
par[dsu(u)] = dsu(v);
mn += parity(dsu(v));
}
int solve(int d){
// cout << "D is " << d << "\n";
// int sz = idxB.size();
vector <int> left(n + 1), right(n + 1), mx(n + 1);
int j = 0;
for (auto i : idxB) {
int wei = artifactsB[j++];
int l = lower_bound(artifactsB.begin(), artifactsB.end(), wei - d) - artifactsB.begin();
int r = upper_bound(artifactsB.begin(), artifactsB.end(), wei + d) - artifactsB.begin() - 1;
left[i] = l;
right[i] = r;
}
j = 0;
vector <pii> intervals;
for (auto i : idxB) {
// int ii = artifacts[i].second;
// cout << i << ": idx is " << ii << ": weight is " << artifactsB[j++] << ": bounds are " << left[i] << ", " << right[i] << ": there are " << right[i] - left[i] + 1 << " in the range" << "\n";
if (intervals.empty() || left[i] > intervals.back().second) intervals.emb(left[i], right[i]);
else intervals.back().second = max(intervals.back().second, right[i]);
}
int ans = sum;
for (auto [l, r] : intervals) {
// cout << "[" << l << ", " << r << "]\n";
if ((r - l + 1) % 2 == 0) continue;
int cur = inf;
for (int i = l; i <= r; i++) {
if ((i - l) % 2 == 0) cur = min(cur, Aprices[i]);
else if (i != l && i != r && artifactsB[i + 1] - artifactsB[i - 1] <= d) cur = min(cur, Aprices[i]);
}
ans += cur;
}
// cout << "--------------------------------------------------------------\n";
return ans;
}
vector <int> calculate_costs(vector<int32_t> ww, vector<int32_t> aa, vector<int32_t> bb, vector<int32_t> e) {
n = ww.size();
iota(par, par + n, 0ll);
// int32_t q = (int32_t)e.size();
for (int32_t i = 0; i < n; i++) {
int mnn = min(aa[i], bb[i]);
sum += bb[i];
w[i + 1] = ww[i];
a[i + 1] = aa[i] - bb[i];
b[i + 1] = bb[i] - mnn;
if (a[i + 1] == 0) a[i + 1] = inf;
if (b[i + 1] == 0) b[i + 1] = inf;
if (a[i + 1] == inf) alone[i + 1] = 1;
artifacts.emb(ww[i], i + 1);
}
sort(all(artifacts));
int q = e.size();
vector <int> r(q);
vector <pii> que;
for (int i = 0; i < q; i++) {
que.emb(e[i], i);
}
sort(all(que));
vector <tiii> events;
for (int i = 1; i < n; i++) {
events.emb(artifacts[i + 1].first - artifacts[i].first, 0, i);
}
for (int i = 2; i < n; i++) {
events.emb(artifacts[i + 1].first - artifacts[i - 1].first, 1, i);
}
sort(all(events));
int j = 0;
for (int i = 1; i <= n; i++) {
int ii = artifacts[i].second;
if (i % 2) oddmin[i] = a[ii], evenmin[i] = inf;
else oddmin[i] = inf, evenmin[i] = a[ii];
specialmin[i] = inf;
sz[i] = 1;
lb[i] = i;
rb[i] = i;
mn += parity(i);
}
for (auto [dis, type, idxx] : events) {
while (j < q && que[j].first < dis) {
r[que[j].second] = sum + mn;
j++;
}
if (type == 0) { // normal merge
unite(idxx, idxx + 1);
}
else { // special min
mn -= parity(dsu(idxx));
specialmin[dsu(idxx)] = min(specialmin[dsu(idxx)], a[artifacts[idxx].second]);
mn += parity(dsu(idxx));
}
}
while (j < q) {
r[que[j].second] = sum + mn;
j++;
}
return r;
}
// int32_t main() {
// // Example test case input
// // int N = 5;
// vector<int32_t> W = {15, 12, 2, 10, 21};
// vector<int32_t> A = {5, 4, 5, 6, 3};
// vector<int32_t> B = {1, 2, 2, 3, 2};
// vector<int32_t> E = {5, 9, 1};
// vector<int> results = calculate_costs(W, A, B, E);
// for (auto res : results) {
// cout << res << endl;
// }
// return 0;
// }
