#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
#include<set>
#include "wiring.h"
using namespace std;
vector<int> st(20);
void build(int node, int r_begin, int r_end, vector<int>&vector){
if(r_begin == r_end){
st[node] = vector[r_begin];
return;
}
else{
int mid = (r_begin+r_end)/2;
build(2*node,r_begin,mid,vector);
build(2*node+1,mid+1,r_end,vector);
st[node] = max(st[2*node],st[2*node+1]);
}
}
int query(int node, int r_begin, int r_end, int ql, int qr){
if(r_begin>qr || r_end<ql){
return 0;
}
if(r_begin>=ql && r_end<=qr){
return st[node];
}
int mid = (r_begin+r_end)/2;
return max(query(2*node,r_begin,mid,ql,qr),query(2*node+1,mid+1,r_end,ql,qr));
}
void update(int node, int r_begin, int r_end, int idx, int val){
if(r_begin == r_end){
st[node] = val;
return;
}
else{
int mid = (r_begin+r_end)/2;
if(idx<=mid){
update(2*node,r_begin,mid,idx,val);
}
else{
update(2*node+1,mid+1,r_end,idx,val);
}
st[node] = max(st[2*node],st[2*node+1]);
}
}
long long wire_length(vector<int> &l_a, int l_a_size, vector<int> &s_a, int s_a_size){
long long length = 0;
map<int,int> mp;
vector<pair<int,int>> multiple_connections;
set<int> s_a_set;
int size = s_a[s_a_size-1]+1;
vector<int> plugged(size,0);
for(int i = 0; i < s_a_size; i++){
mp.insert({s_a[i],i});
s_a_set.insert(s_a[i]);
}
build(1,0,s_a_size-1,s_a);
for(int j = 0; j < l_a_size; j++){
auto s = upper_bound(s_a.begin(),s_a.end(),l_a[j]);
int index = mp[*s];
if(s==s_a.end()){
int end_index = s_a_size-1;
int num = query(1,0,s_a_size-1,0,end_index);
if(num == 0){
length+=abs(s_a[end_index]-l_a[j]);
plugged[s_a[end_index]]+=1;
if(plugged[s_a[end_index]]==1){
s_a_set.erase(s_a[end_index]);
}
}
else{
int max_index = mp[num];
length += abs(s_a[max_index] - l_a[j]);
plugged[s_a[max_index]] += 1;
if( plugged[s_a[max_index]]==1){
s_a_set.erase(s_a[max_index]);
}
update(1,0,s_a_size-1,max_index,0);
}
}
else if(index == 0){
length += abs(s_a[index]-l_a[j]);
plugged[s_a[index]] += 1;
if(plugged[s_a[index]] > 1){
multiple_connections.push_back({l_a[j],abs(s_a[index]-l_a[j])});
}
if(plugged[s_a[index]] == 1){
s_a_set.erase(s_a[index]);
}
update(1,0,s_a_size-1,index,0);
}
else{
if(plugged[s_a[index-1]]){
int num = query(1,0,s_a_size-1,0,index-1);
if(num == 0){
if(abs(s_a[index-1] - l_a[j]) <= abs(s_a[index] - l_a[j])){
length += abs(s_a[index-1] - l_a[j]);
plugged[s_a[index-1]] += 1;
if( plugged[s_a[index-1]] > 1){
multiple_connections.push_back({l_a[j],abs(s_a[index-1]-l_a[j])});
}
if(plugged[s_a[index-1]] == 1){
s_a_set.erase(s_a[index-1]);
}
}
else{
length += abs(s_a[index] - l_a[j]);
plugged[s_a[index]] += 1;
if(plugged[s_a[index]] > 1){
multiple_connections.push_back({l_a[j],abs(s_a[index]-l_a[j])});
}
if(plugged[s_a[index]]==1){
s_a_set.erase(s_a[index]);
}
}
}
else{
int max_index = mp[num];
length += abs(s_a[max_index] - l_a[j]);
plugged[s_a[max_index]] += 1;
if(plugged[s_a[max_index]] == 1){
s_a_set.erase(s_a[max_index]);
}
update(1,0,s_a_size-1,max_index,0);
}
}
else{
length += abs(s_a[index-1]-l_a[j]);
plugged[s_a[index-1]] += 1;
if(plugged[s_a[index-1]] == 1){
s_a_set.erase(s_a[index-1]);
}
update(1,0,s_a_size-1,index-1,0);
}
}
}
int m_c_size = multiple_connections.size();
for(int u = m_c_size-1; u >= 0; u--){
if(!s_a_set.empty()){
auto v = upper_bound(s_a_set.begin(),s_a_set.end(),multiple_connections[u].first);
if(v == s_a_set.end()){
continue;
}
else{
length -= multiple_connections[u].second;
length+=abs(multiple_connections[u].first-*v);
s_a_set.erase(*v);
}
}
else{
break;
}
}
return length;
}
long long min_total_length(vector<int> r, vector<int> b){
long long length;
if(r.size() >= b.size()){
length = wire_length(r,r.size(),b,b.size());
}
else{
length = wire_length(b,b.size(),r,r.size());
}
return length;
}
