#include "nile.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> ii;
typedef pair<ll, ii> pii;
#define vi vector<ll>
#define vii vector<ii>
#define vpii vector<pii>
#define whole(x) x.begin(), x.end()
#define fi first
#define se second
#define pb push_back
ll fat[100005], sz[100005], le[100005], ri[100005];
const ll inf = 1000000000000000000;
struct segtree{
ll n;
vi t;
segtree(vi &x){
n = (ll)x.size();
t.assign(4 * n, inf);
build(0, n-1, 1, x);
}
void build(ll l, ll r, ll no, vi &x){
//cout << l << " " << r << endl;
if(l == r){
t[no] = x[l];
return;
}
ll mid = l + (r - l) / 2;
build(l, mid, 2*no, x);
build(mid+1, r, 2*no+1, x);
t[no] = min(t[2*no], t[2*no+1]);
return;
}
void update(ll l, ll r, ll no, ll i, ll val){
assert(i <= r && i >= l);
if(l == r){
t[no] = val;
return;
}
ll mid = l + (r - l) / 2;
if(i <= mid){
update(l, mid, 2*no, i, val);
}else{
update(mid+1, r, 2*no+1, i, val);
}
t[no] = min(t[2*no], t[2*no+1]);
return;
}
ll query(ll l, ll r, ll no, ll lq, ll rq){
if(l == lq && r == rq){
return t[no];
}
ll mid = l + (r - l) / 2;
if(lq > mid){
return query(mid+1, r, 2*no+1, lq, rq);
}else if(rq <= mid){
return query(l, mid, 2*no, lq, rq);
}
ll lef = query(l, mid, 2*no, lq, mid);
ll rig = query(mid+1, r, 2*no+1, mid+1, rq);
return min(lef, rig);
}
};
ll ffather(ll no){
if(fat[no] == no){
return no;
}
return fat[no] = ffather(fat[no]);
}
void join(ll u, ll v){
u = ffather(u);
v = ffather(v);
if(u == v){
return;
}
if(sz[u] < sz[v]){
swap(u, v);
}
fat[v] = u;
sz[u] += sz[v];
le[u] = min(le[u], le[v]);
ri[u] = max(ri[u], ri[v]);
return;
}
std::vector<long long> calculate_costs(std::vector<int> w, std::vector<int> a, std::vector<int> b, std::vector<int> E) {
for(ll i = 0; i < 100005; ++i){
fat[i] = i;
sz[i] = 1;
le[i] = i;
ri[i] = i;
}
ll n = ll(a.size());
vpii x;
ll sum = 0;
for(ll i = 0; i < ll(w.size()); ++i){
sum += 1LL * a[i];
x.pb({1LL * w[i], {1LL * a[i], 1LL * b[i]}});
}
vi even;
vi odd;
sort(whole(x));
vii op;
vii sop;
even.pb(x[0].se.fi - x[0].se.se);
odd.pb(inf);
for(int i = 1; i < (int)x.size(); ++i){
if(i % 2 == 0){
even.pb(x[i].se.fi - x[i].se.se);
odd.pb(inf);
}else{
odd.pb(x[i].se.fi - x[i].se.se);
even.pb(inf);
}
if(i == (int)x.size()-1){
op.pb({x[i].fi - x[i-1].fi, i});
continue;
}
op.pb({x[i].fi - x[i-1].fi, i});
sop.pb({x[i+1].fi - x[i-1].fi, i});
}
segtree oddtree(odd);
segtree eventree(even);
sort(whole(op));
sort(whole(sop));
vii q;
for(ll i = 0; i < (ll)E.size(); ++i){
q.pb({E[i], i});
}
sort(whole(q));
std::vector<long long> ans((ll)q.size(), 0);
ll i = 0;
ll j = 0;
for(auto k:q){
ll val = k.fi;
//cout << val << " ." << endl;
unordered_set<ll> tocheck;
while(i < (ll)op.size() && op[i].fi <= val){
ll v = op[i].se;
ll u = v-1;
v = ffather(v);
u = ffather(u);
if(u == v){
i++;
continue;
}
if((sz[v] % 2) == 1 && tocheck.find(v) == tocheck.end()){
if(le[v] % 2 == 0){
sum -= eventree.query(0, n-1, 1, le[v], ri[v]);
}else{
sum -= oddtree.query(0, n-1, 1, le[v], ri[v]);
}
}
//cout << u << " " << v << " " << sum << endl;
if((sz[u] % 2) == 1 && tocheck.find(u) == tocheck.end()){
if(le[u] % 2 == 0){
sum -= eventree.query(0, n-1, 1, le[u], ri[u]);
}else{
sum -= oddtree.query(0, n-1, 1, le[u], ri[u]);
}
}
//cout << u << " " << v << " " << sum << endl;
join(u, v);
tocheck.insert(ffather(u));
i++;
}
while(j < (ll)sop.size() && sop[j].fi <= val){
ll u = sop[j].se;
ll ff = ffather(u);
if(sz[ff] % 2 == 1 && tocheck.find(ff) == tocheck.end()){
if(le[ff] % 2 == 0){
sum -= eventree.query(0, n-1, 1, le[ff], ri[ff]);
}else{
sum -= oddtree.query(0, n-1, 1, le[ff], ri[ff]);
}
}
tocheck.insert(ff);
//cout << u << " " << sop[j].fi << endl;
if(u % 2 == 0){
oddtree.update(0, n-1, 1, u, x[u].se.fi - x[u].se.se);
}else{
eventree.update(0, n-1, 1, u, x[u].se.fi - x[u].se.se);
}
j++;
}
//cout << eventree.query(0, n-1, 1, 0, 4) << endl;
unordered_set<ll> checktocheck;
for(auto e:tocheck){
e = ffather(e);
if(sz[e] % 2 == 1 && checktocheck.find(e) == checktocheck.end()){
if(le[e] % 2 == 0){
sum += eventree.query(0, n-1, 1, le[e], ri[e]);
}else{
sum += oddtree.query(0, n-1, 1, le[e], ri[e]);
}
}
checktocheck.insert(e);
}
ans[k.se] = sum;
}
return ans;
}
