#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct SEG{
vector<ll>seg;
void init(ll n){
seg.resize(4*n+5);
}
void upd(ll ul, ll l, ll r, ll val, ll id){
if(l==r){
seg[id]+=val; return;
}
ll mid=(l+r)>>1;
if(ul<=mid)upd(ul,l,mid,val,id*2);
else upd(ul,mid+1,r,val,id*2+1);
seg[id]=seg[id*2]+seg[id*2+1];
}
ll qry(ll ql, ll qr, ll l, ll r, ll id){
if(l>qr||r<ql)return 0;
if(l>=ql&&r<=qr)return seg[id];
ll mid=(l+r)>>1;
return qry(ql,qr,l,mid,id*2)+qry(ql,qr,mid+1,r,id*2+1);
}
};
struct DSU{
vector<ll>fa,siz,val;
void init(ll n){
fa.resize(n+5);
siz.resize(n+5); val.resize(n+5);
for(int i=0;i<n+5;i++){
fa[i]=i; siz[i]=1; val[i]=i;
}
}
ll root(ll x){
if(fa[x]==x)return x;
return fa[x]=root(fa[x]);
}
void unite_left(ll u, ll v){
u=root(u); v=root(v);
if(siz[u]<siz[v])swap(u,v);
siz[u]+=siz[v]; fa[v]=u;
val[u]=min(val[u],val[v]);
}
void unite_right(ll u, ll v){
u=root(u); v=root(v);
if(siz[u]<siz[v])swap(u,v);
siz[u]+=siz[v]; fa[v]=u;
val[u]=max(val[u],val[v]);
}
ll value(ll x){
x=root(x);
return val[x];
}
void clear(){
fa.clear(); siz.clear(); val.clear();
}
};
ll a[600005],b[300005],c[300005];
ll discval[600005];
vector<pair<ll,ll> > inpos[600005],outpos[600005];
ll enterin[600005],enterout[600005];
ll n; ll pos;
ll curid;
ll diff;
vector<pair<ll,ll> >disc;
ll val(pair<ll,ll> x){
return lower_bound(disc.begin(),disc.end(),x)-disc.begin()+1;
}
bool valid(ll st){
// b/c pos[a[curid]] with a[curid]
bool in=0;
if(st<=curid&&curid<=st+n-1)in=1;
if(in){
ll aite=-1;
for(int i=0;i<inpos[curid].size()-1;i++){
if(inpos[curid][i].first<=st&&st<=inpos[curid][i+1].first){
if(inpos[curid][i].first>=pos&&inpos[curid][i+1].first>=pos){
ll dff=inpos[curid][i+1].second-inpos[curid][i].second;
aite=inpos[curid][i+1].second-min(dff,inpos[curid][i+1].first-st); break;
}
else{
ll dff=inpos[curid][i].second-inpos[curid][i+1].second;
aite=inpos[curid][i].second-min(dff,st-inpos[curid][i].first); break;
}
}
}
ll df=abs(b[aite]-a[curid]);
if(df<=diff)return 1;
return 0;
}
else{
ll aite=-1;
for(int i=0;i<outpos[curid].size()-1;i++){
if(outpos[curid][i].first<=st&&st<=outpos[curid][i+1].first){
if(outpos[curid][i].first>=pos&&outpos[curid][i+1].first>=pos){
ll dff=outpos[curid][i].second-outpos[curid][i+1].second;
aite=outpos[curid][i+1].second+min(dff,outpos[curid][i+1].first-st); break;
}
else{
ll dff=outpos[curid][i+1].second-outpos[curid][i].second;
aite=outpos[curid][i].second+min(dff,st-outpos[curid][i].first); break;
}
}
}
ll df=abs(c[aite]-a[curid]);
if(df<=diff)return 1;
return 0;
}
}
bool remove(DSU& lef, DSU& righ, ll ql, ll qr, bool front){
if(front){
ll lst=righ.value(ql);
if(lst>qr)return 0;
if(!valid(lst)){
righ.unite_right(lst,lst+1); lef.unite_left(lst,lst-1); return 1;
}
return 0;
}
else{
ll vl=lef.value(qr);
if(vl<ql)return 0;
if(!valid(vl)){
righ.unite_right(vl,vl+1); lef.unite_left(vl,vl-1); return 1;
}
return 0;
}
}
bool ck(ll lambda){
diff=lambda;
DSU lef,righ;
lef.init(n); righ.init(n);
for(int i=1;i<=2*n;i++){
curid=i;
if(i<=n){
// 1 to i: inside, i+1 to n+1: outside
if(pos<=i){
while(remove(lef,righ,1,pos,1));
while(remove(lef,righ,1,pos,0));
while(remove(lef,righ,pos,i,1));
while(remove(lef,righ,pos,i,0));
while(remove(lef,righ,i+1,n+1,1));
while(remove(lef,righ,i+1,n+1,0));
}
else{
while(remove(lef,righ,1,i,1));
while(remove(lef,righ,1,i,0));
while(remove(lef,righ,i+1,pos,1));
while(remove(lef,righ,i+1,pos,0));
while(remove(lef,righ,pos,n+1,1));
while(remove(lef,righ,pos,n+1,0));
}
}
else{
// 1 to i-n: outside, i-n+1 to n+1: inside
if(pos<=i-n){
while(remove(lef,righ,1,pos,1));
while(remove(lef,righ,1,pos,0));
while(remove(lef,righ,pos,i-n,1));
while(remove(lef,righ,pos,i-n,0));
while(remove(lef,righ,i-n+1,n+1,1));
while(remove(lef,righ,i-n+1,n+1,0));
}
else{
while(remove(lef,righ,1,i-n,1));
while(remove(lef,righ,1,i-n,0));
while(remove(lef,righ,i-n+1,pos,1));
while(remove(lef,righ,i-n+1,pos,0));
while(remove(lef,righ,pos,n+1,1));
while(remove(lef,righ,pos,n+1,0));
}
}
}
if(righ.value(1)<=n+1)return 1;
lef.clear(); righ.clear();
lef.init(n); righ.init(n);
for(int i=1;i<=n;i++){
swap(b[i],c[i]);
}
for(int i=1;i<=2*n;i++){
curid=i;
if(i<=n){
// 1 to i: inside, i+1 to n+1: outside
if(pos<=i){
while(remove(lef,righ,1,pos,1));
while(remove(lef,righ,1,pos,0));
while(remove(lef,righ,pos,i,1));
while(remove(lef,righ,pos,i,0));
while(remove(lef,righ,i+1,n+1,1));
while(remove(lef,righ,i+1,n+1,0));
}
else{
while(remove(lef,righ,1,i,1));
while(remove(lef,righ,1,i,0));
while(remove(lef,righ,i+1,pos,1));
while(remove(lef,righ,i+1,pos,0));
while(remove(lef,righ,pos,n+1,1));
while(remove(lef,righ,pos,n+1,0));
}
}
else{
// 1 to i-n: outside, i-n+1 to n+1: inside
if(pos<=i-n){
while(remove(lef,righ,1,pos,1));
while(remove(lef,righ,1,pos,0));
while(remove(lef,righ,pos,i-n,1));
while(remove(lef,righ,pos,i-n,0));
while(remove(lef,righ,i-n+1,n+1,1));
while(remove(lef,righ,i-n+1,n+1,0));
}
else{
while(remove(lef,righ,1,i-n,1));
while(remove(lef,righ,1,i-n,0));
while(remove(lef,righ,i-n+1,pos,1));
while(remove(lef,righ,i-n+1,pos,0));
while(remove(lef,righ,pos,n+1,1));
while(remove(lef,righ,pos,n+1,0));
}
}
}
if(righ.value(1)<=n+1)return 1;
return 0;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n;
for(int i=1;i<=2*n;i++)cin>>a[i];
for(int i=1;i<=n;i++)cin>>b[i];
for(int i=1;i<=n;i++)cin>>c[i];
sort(b+1,b+n+1); sort(c+1,c+n+1);
ll lol=*max_element(a+1,a+2*n+1)-min(*min_element(b+1,b+n+1),*min_element(c+1,c+n+1));
lol=max(lol,max(*max_element(b+1,b+n+1),*max_element(c+1,c+n+1))-*min_element(a+1,a+2*n+1));
pos=n+1;
for(int i=1;i<=n;i++){
if(a[i]>a[i+n]){
pos=i; break;
}
}
for(int i=1;i<=2*n;i++)disc.push_back({a[i],i});
sort(disc.begin(),disc.end());
SEG ins,outs;
ins.init(2*n); outs.init(2*n);
for(int i=1;i<=2*n;i++){
discval[i]=val({a[i],i});
}
for(int i=1;i<=n;i++){
ins.upd(discval[i],1,2*n,1,1);
outs.upd(discval[i+n],1,2*n,1,1);
}
for(int i=1;i<=n;i++){
enterin[i]=ins.qry(1,discval[i],1,2*n,1);
enterout[i+n]=outs.qry(1,discval[i+n],1,2*n,1);
inpos[i].push_back({1,enterin[i]});
outpos[i+n].push_back({1,enterout[i+n]});
if(i==1){
inpos[i].push_back({1,enterin[i]});
outpos[i+n].push_back({1,enterout[i+n]});
}
}
for(int i=2;i<=n+1;i++){
ins.upd(discval[i-1],1,2*n,-1,1);
ins.upd(discval[i+n-1],1,2*n,1,1);
outs.upd(discval[i-1],1,2*n,1,1);
outs.upd(discval[i+n-1],1,2*n,-1,1);
if(i==pos){
for(int j=1;j<=2*n;j++){
bool in=0;
if(i<=j&&i+n-1>=j)in=1;
if(in){
ll vl=ins.qry(1,discval[j],1,2*n,1);
inpos[j].push_back({i,vl});
}
else{
ll vl=outs.qry(1,discval[j],1,2*n,1);
outpos[j].push_back({i,vl});
}
}
}
enterout[i-1]=outs.qry(1,discval[i-1],1,2*n,1);
enterin[i+n-1]=ins.qry(1,discval[i+n-1],1,2*n,1);
inpos[i+n-1].push_back({i,enterin[i+n-1]});
outpos[i-1].push_back({i,enterout[i-1]});
inpos[i].push_back({i,ins.qry(1,discval[i],1,2*n,1)});
outpos[i+n].push_back({i,outs.qry(1,discval[i+n],1,2*n,1)});
}
for(int i=1;i<=2*n;i++){
sort(inpos[i].begin(),inpos[i].end());
sort(outpos[i].begin(),outpos[i].end());
}
ll l=0,r=lol;
while(l<r){
ll mid=(l+r)>>1;
if(ck(mid))r=mid;
else l=mid+1;
}
cout<<l<<'\n';
}
