#include "nile.h"
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ll long long
#define vi vector<ll>
#define pb push_back
#define f0r(i,n) for(int i = 0; i<n;i++)
#define pii pair<ll,ll>
using namespace std;
//using namespace __gnu_pbds;
const int mxn = 100005;
vector<vi> tree(mxn*4, vi(4, 4e18));
//good, odd
//good, even
//bad, odd
//bad, even
int n;
void upd(int k, ll x, int t){
k += n;
tree[k][t] = x;
for(k /= 2; k>=1; k/=2){
tree[k][t] = min(tree[k*2][t], tree[k*2+1][t]);
}
}
ll quer(int l, int r, int t){
l += n;
r += n;
ll ret = 4e18;
while(l <= r){
if(l % 2 == 1){
if(ret > tree[l][t]){
ret = tree[l][t];
}
l++;
}
if(r % 2 == 0){
if(ret > tree[r][t]){
ret = tree[r][t];
}
r--;
}
l/=2;
r/=2;
}
return ret;
}
vi sz(mxn, 1);
vi par(mxn, 0);
vector<pair<ll,ll>>rng(mxn);
vi anst(mxn);
ll ca = 0;
int get(int x){
while(par[x] != x)x = par[x];
return x;
}
pair<ll,ll> mrg(pii a, pii b){
if(a > b)swap(a, b);
return {a.first, b.second};
}
void unite(int a, int b){
//cout<<a<<' '<<b<<'\n';
a = get(a);
b = get(b);
if(sz[a] < sz[b])swap(a, b);
par[b] = a;
sz[a] += sz[b];
ca -= anst[a];
ca -= anst[b];
//cout<<anst[a]<<' '<<anst[b]<<'\n';
rng[a] = mrg(rng[a], rng[b]);
//cout<<rng[a].first<<' '<<rng[a].second<<'\n';
//ca += (sz[a] % 2);
int l = rng[a].first;
int r = rng[a].second;
if((r - l + 1) % 2 == 0)anst[a] = 0;
else{
if(l % 2 == 1){
anst[a] = min(quer(l, r, 0), quer(l, r, 3));
}
else anst[a] = min(quer(l, r, 1), quer(l, r, 2));
}
//cout<<anst[a]<<'\n';
ca += anst[a];
//cout<<ans[a]<<' '<<ans[b]<<' '<<(sz[a] % 2)<<'\n';
//ans[a] = (sz[a] % 2);
//cout<<a<<' '<<ans[a]<<'\n';
//cout<<'\n';
}
std::vector<long long> calculate_costs(std::vector<int> w, std::vector<int> a,
std::vector<int> b, std::vector<int> e) {
int q = e.size();
n = w.size();
f0r(i, n){
par[i] = i;
rng[i] = {i,i};
}
vi ans(q, 0);
vector<pair<ll,ll>>quers;
f0r(i, q)quers.pb({e[i], i});
sort(quers.begin(), quers.end());
ll s=0;
f0r(i,n)s += b[i];
vi c(n);
f0r(i, n){
c[i] = a[i] - b[i];
}
ca = 0;
f0r(i, n)ca += c[i];
//cout<<ca<<'\n';
vector<pair<ll,ll>>tmp;
f0r(i,n){
tmp.pb({w[i], c[i]});
}
sort(tmp.begin(), tmp.end());
f0r(i, n){
w[i] = tmp[i].first;
c[i] = tmp[i].second;
}
f0r(i, n)anst[i] = c[i];
//for(auto u : c)cout<<u<<' ';
//cout<<'\n';
vector<pair<ll,ll>>connectors;
f0r(i, n-1){
connectors.pb({w[i+1] - w[i], i});
}
sort(connectors.begin(), connectors.end());
vector<pair<ll,ll>>mids;
for(int i = 1; i<n-1; i++){
mids.pb({w[i+1] - w[i-1], i});
}
sort(mids.begin(), mids.end());
vector<pair<pair<int,int>,int>>ranges;
f0r(i,n)ranges.pb({{i,i}, c[i]});
int p1 = 0;
int p2 = 0;
f0r(i, n){
if(i % 2 == 1){
upd(i, c[i], 0);
}
else upd(i, c[i], 1);
}
f0r(tt, q){
ll k = quers[tt].first;
//cout<<k<<'\n';
while(p2 < n-2 && k >= mids[p2].first){
int dex = mids[p2].second;
if(dex % 2 == 1){
upd(dex, c[dex], 2);
}
else{
upd(dex, c[dex], 3);
}
int parr = get(dex);
if(anst[parr] > c[dex]){
ca -= anst[parr];
ca += c[dex];
anst[parr] = c[dex];
}
p2++;
}
while(p1 < n-1 && k >= connectors[p1].first){
int dex = connectors[p1].second;
/*
int l = 0; int r = ranges.size();
while(l < r){
int mid = (l + r)/2;
if(ranges[mid].first.first < )
}
*/
unite(dex, dex + 1);
p1++;
}
//cout<<ca<<'\n';
/*
ll curans = 0;
ll cs = 0;
vector<pair<int,int>>ranges;
f0r(j, n-1){
if(w[j+1] - w[j] > k){
ranges.pb({cs, j});
cs = j+1;
}
}
ranges.pb({cs, n-1});
//for(auto u : ranges)cout<<u.first<<' '<<u.second<<'\n';
f0r(i, ranges.size()){
int l = ranges[i].first;
int r = ranges[i].second;
if((r - l + 1) % 2 == 1){
ll cur = 4e18;
for(int j = l; j<=r; j++){
if((j - l) % 2 == 0)cur = min(cur, c[j]);
else{
if(w[j+1] - w[j-1] <= k)cur = min(cur, c[j]);
}
}
//cout<<cur<<"cur"<<'\n';
curans += cur;
}
}
*/
ans[tt] = s + ca;
//cout<<ca<<'\n';
//cout<<'\n';
}
vi anss(q);
f0r(i,q){
anss[quers[i].second] = ans[i];
}
return anss;
}
