#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
#define pb push_back
typedef long long ll;
const ll mxN=2e6+5;
const ll inf=1e18;
ll n;
ll a[mxN];
vll b, c;
bool pos[mxN][2];
void solve(){
cin>>n;
for(ll i=0;i<2*n;i++){
cin>>a[i];
a[i+2*n]=a[i];
}
b=vll(n);
for(auto &it:b){
cin>>it;
}
c=vll(n);
for(auto &it:c){
cin>>it;
}
sort(b.begin(), b.end());
sort(c.begin(), c.end());
auto qry=[&](ll tar, ll diff, ll flag){
if(flag==0){
ll mx=tar+diff;
ll lef=0, rig=n-1;
ll good1=-1;
while(lef<=rig){
ll mid=(lef+rig)/2;
if(b[mid]<=mx){
good1=mid;
lef=mid+1;
}
else{
rig=mid-1;
}
}
// if(good1!=-1 && b[good1]<tar){
// good1=-1;
// }
ll mn=tar-diff;
lef=0;
rig=n-1;
ll good2=n;
while(lef<=rig){
ll mid=(lef+rig)/2;
if(b[mid]>=mn){
good2=mid;
rig=mid-1;
}
else{
lef=mid+1;
}
}
// if(good2!=n && b[good2]>tar){
// good2=n;
// }
if(good2>good1){
return make_pair(n, -1LL);
}
return make_pair(good2, good1);
}
else{
ll mx=tar+diff;
ll lef=0, rig=n-1;
ll good1=-1;
while(lef<=rig){
ll mid=(lef+rig)/2;
if(c[mid]<=mx){
good1=mid;
lef=mid+1;
}
else{
rig=mid-1;
}
}
// if(good1!=-1 && c[good1]<tar){
// good1=-1;
// }
ll mn=tar-diff;
lef=0;
rig=n-1;
ll good2=n;
while(lef<=rig){
ll mid=(lef+rig)/2;
if(c[mid]>=mn){
good2=mid;
rig=mid-1;
}
else{
lef=mid+1;
}
}
// if(good2!=n && c[good2]>tar){
// good2=n;
// }
if(good2>good1){
return make_pair(n, -1LL);
}
return make_pair(good2, good1);
}
};
vll v(2*n);
ll pt=2*n;
for(ll i=0;i<n;i++){
while(pt-1>=n && a[pt-1]<a[i]){
pt--;
}
v[i]=pt;
}
pt=-1;
for(ll i=2*n-1;i>=n;i--){
while(pt+1<n && a[pt+1]<=a[i]){
pt++;
}
v[i]=pt;
}
auto dumb=[&](ll idx){
return v[idx];
};
vll bad_cnt(2*n);
auto mark=[&](ll lef, ll rig){
// cout<<"marking "<<lef<<' '<<rig<<'\n';
if(lef<=rig){
bad_cnt[lef]++;
if(rig<2*n-1) bad_cnt[rig+1]--;
}
else{
bad_cnt[lef]++;
bad_cnt[0]++;
if(rig<2*n-1) bad_cnt[rig+1]--;
}
};
auto dis=[&](ll f, ll s){
if(f<s){
return s-f;
}
else{
return s+2*n-f;
}
};
auto end_to_start=[&](ll tar){
ll re=tar-n+1+2*n;
re%=2*n;
return re;
};
auto check=[&](ll diff){
memset(pos, 0, sizeof(pos));
for(ll rep=0;rep<2;rep++){
// cout<<"rep: "<<rep<<'\n';
bad_cnt=vll(2*n, 0);
for(ll i=0;i<n;i++){
// cout<<"considering "<<i<<'\n';
pll p=qry(a[i], diff, rep);
// cout<<"range: "<<p.F<<' '<<p.S<<'\n';
if(p.F==n){
mark((i-n+1+2*n)%(2*n), i);
}
else{
ll tep=dumb(i);
if(tep==2*n){
if(p.F>i){
mark((i-n+1+2*n)%(2*n), i);
}
else{
if(p.S<i){
if(i-p.S-1>=i-n+1) mark((i-n+1+2*n)%(2*n), (i-p.S-1+2*n)%(2*n));
}
if(p.F>0){
if(i-p.F+1>=i-n+1) mark(((i-p.F+1+2*n)%(2*n)), i);
else mark((i-n+1+2*n)%(2*n), i);
}
}
continue;
}
ll d=dis(tep, i);
if(d<p.F){
mark((i-n+1+2*n)%(2*n), i);
}
else{
if(p.F>0){
if(tep<=i+n-1 && i+n-tep>=p.F){
}
else{
// cout<<"hi2\n";
if(i-p.F+1>=i-n+1) mark(((i-p.F+1+2*n)%(2*n)), i);
else mark((i-n+1+2*n)%(2*n), i);
}
}
if(p.S<d){
ll bk=tep-n+1;
if(bk<=i && i-bk+1>p.S){
mark((i-n+1+2*n)%(2*n), i);
}
else{
// cout<<"hi\n";
if(i-p.S-1>=i-n+1) mark((i-n+1+2*n)%(2*n), (i-p.S-1+2*n)%(2*n));
}
}
}
}
}
for(ll i=n;i<2*n;i++){
// cout<<"considering "<<i<<'\n';
pll p=qry(a[i], diff, rep);
// cout<<"range: "<<p.F<<' '<<p.S<<'\n';
if(p.F==n){
mark((i-n+1+2*n)%(2*n), i);
}
else{
ll tep=dumb(i);
if(tep==-1){
if(p.F>2*n-1-i){
mark((i-n+1+2*n)%(2*n), i);
}
else{
if(p.F>0){
mark(end_to_start(i), end_to_start((i+p.F-1)%(2*n)));
}
if(p.S<2*n-1-i){
mark(end_to_start((i+p.S+1)%(2*n)), i);
}
}
continue;
}
ll d=dis(i, tep);
// cout<<"d: "<<d<<'\n';
if(d<p.F){
mark((i-n+1+2*n)%(2*n), i);
}
else{
if(p.F>0){
ll st=end_to_start(i);
if(st<=tep && tep-st+1>=p.F){
}
else{
if(i+p.F-1<=i+n-1) mark(end_to_start(i), end_to_start((i+p.F-1)%(2*n)));
else mark((i-n+1+2*n)%(2*n), i);
}
}
if(p.S<d){
ll st=end_to_start(i);
if(st<=tep && tep-st+1>p.S){
mark((i-n+1+2*n)%(2*n), i);
}
else{
// cout<<"hi3\n";
if(i+p.S+1<=i+n-1) mark(end_to_start((i+p.S+1)%(2*n)), i);
}
}
}
}
}
if(bad_cnt[0]==0){
pos[0][rep]=1;
}
for(ll i=1;i<2*n;i++){
bad_cnt[i]+=bad_cnt[i-1];
if(bad_cnt[i]==0){
pos[i][rep]=1;
}
}
// cout<<"_______________\n";
}
for(ll i=0;i<n;i++){
if((pos[i][0] && pos[i+n][1]) || (pos[i][1] && pos[i+n][0])){
return true;
}
}
return false;
};
// bool tep=check(2);
// cout<<"tep: "<<tep<<'\n';
ll lef=0, rig=1e9+5;
ll ans=-1;
while(lef<=rig){
ll mid=(lef+rig)/2;
if(check(mid)){
ans=mid;
rig=mid-1;
}
else{
lef=mid+1;
}
}
cout<<ans<<'\n';
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
