#include<bits/stdc++.h>
#include "nile.h"
using namespace std;
using ll = long long;
vector<pair<int , int>> arr , e , arrtwo;
vector<pair<int , pair<int , int>>> w;
int n , q , par[1000001] , choto[1000001] , koita[1000001] , jor[2][100001] , uno , dos; // ek = min odd
long long sum , one , two , uttor ;
int st[400001] , bam[100001] , dan[100001];
void update( int node , int l , int r , int idx ) {
if( l == r ) st[node] = w[idx].second.first - w[idx].second.second;
else{
int m = ( l + r ) / 2;
if( idx <= m ) update(node * 2 , l , m , idx );
else update( (node * 2) + 1 , m + 1 , r , idx );
st[node] = min( st[node * 2] , st[(node * 2) + 1] );
}
}
void getans( int node , int l , int r , int shu , int she ) {
if( l >= shu && r <= she ) uno = min( uno , st[node] );
else{
int m = (l + r ) / 2;
if( shu <= m ) getans( node * 2 , l , m , shu , she );
if( she >= m + 1 ) getans( (node * 2) + 1 , m + 1, r , shu , she );
cerr << "bruh" << "\n";
}
}
int findpar( int me ) {
if( par[me] == me ) return me;
else{
par[me] = findpar( par[me] );
return par[me];
}
}
void uttorbanao( int me ) {
uttor -= (ll)choto[me];
choto[me] = 0;
if( koita[me] % 2 == 1 ) {
dos = jor[bam[me] % 2][me];
uno = 1e9 + 2;
getans( 1 , 0 , n - 1 , bam[me] , dan[me] );
uno = min( uno , dos );
choto[me] = uno;
uttor += (ll)choto[me];
}
}
void comb( int a , int b ) {
int aa = findpar( a );
int bb = findpar( b );
if( koita[aa] < koita[bb] ) swap( aa , bb );
uttor -= choto[aa];
uttor -= choto[bb];
choto[aa] = 0;
par[bb] = aa;
koita[aa] += koita[bb];
jor[0][aa] = min( jor[0][aa] , jor[0][bb]);
jor[1][aa] = min( jor[1][aa] , jor[1][bb] );
bam[aa] = min( bam[aa] , bam[bb] );
dan[aa] = max( dan[aa] , dan[bb] );
uttorbanao( aa );
}
vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
n = (int)W.size();
q = (int)E.size();
w.clear();
e.clear();
for( int z = 0; z < n; z++ ){
w.push_back({W[z] , {A[z] , B[z]}});
}
for( int z = 0; z < q; z++ ){
e.push_back({E[z] , z});
}
sort( e.begin() , e.end() );
sort( w.begin() , w.end() );
arr.clear();
arrtwo.clear();
for( int z = 1; z < n; z++ ) {
arr.push_back({w[z].first - w[z - 1].first , (z - 1) }); // n - 1
}
for( int z = 1; z < n - 1; z++ ) {
arrtwo.push_back({w[z + 1].first - w[z - 1].first , z}); // size n - 2
}
sort( arr.begin() , arr.end() );
sort( arrtwo.begin() , arrtwo.end() );
uttor = 0;
for( int z = 0; z < n; z++ ) {
choto[z] = w[z].second.first - w[z].second.second; // min tar sathe koto jog kora hocche
par[z] = z;
koita[z] = 1;
uttor += (ll)w[z].second.first;
jor[z % 2][z] = choto[z];
jor[1 - (z % 2)][z] = 1e9 + 2;
bam[z] = z;
dan[z] = z;
}
int here = 0;
int heretwo = 0;
vector<long long> ans(q);
for( int z = 0; z <= 4 * n; z++ ) st[z] = 1e9 + 2;
for( int z = 0; z < q; z++ ) {
while( heretwo < (n - 2) && e[z].first >= arrtwo[heretwo].first ) {
int lol = arrtwo[heretwo].second;
int lmao = findpar( lol );
update( 1 , 0 , n - 1 , lol );
jor[lol % 2][lmao] = min( jor[lol % 2][lmao] , jor[lol % 2][lol] );
jor[1 - (lol % 2)][lmao] = min( jor[1 - (lol % 2)][lmao] , jor[1 - (lol % 2)][lol] );
uttorbanao(lmao);
heretwo++;
}
while( here < n - 1 && e[z].first >= arr[here].first ) {
comb( arr[here].second , arr[here].second + 1 );
here++;
}
ans[e[z].second] = uttor;
for( int y = 0; y < n; y++ ) {
cerr << choto[y] << " " << par[y] << "\n";
}
cerr << "\n";
}
return ans;
}
