#ifndef LOCAL #pragma GCC Optimize("O3,Ofast,unroll-loops") #pragma GCC Target("bmi,bmi2,avx,avx2") #endif #include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; #define int ll #define f first #define s second #define mp make_pair #define pb push_back #define pii pair<int, int> #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin() (x).rend() #ifndef LOCAL #define endl "\n" #endif mt19937 rnd(11); vector<int> solve(vector<int> &a, vector<int> &b, int x) { int n = a.size() / 2; auto calc = [&](int i) { vector<int> now; for (int j = 0; j < n; ++j) { now.pb(a[i + j]); } sort(all(now)); int ans = 0; for (int j = 0; j < n; ++j) { ans = max(ans, abs(now[j] - b[j])); } return ans; }; int ind = 0; for (int i = 1; i < n; ++i) { if (a[i - 1] < a[n + i - 1] && a[i] >= a[n + i]) { ind = i; } } vector<int> ans(n, 0); auto get = [&](int l, int r, auto &&calc) { int sl = l, sr = r; while (r - l > 2) { int m1 = (l * 2 + r) / 3; int m2 = (l + 2 * r) / 3; if (calc(m1) < calc(m2)) { r = m2; } else { l = m1; } } int best = -1; if (calc(l) <= x) { best = l; } else if (calc((l + r) / 2) <= x) { best = (l + r) / 2; } else if (calc(r) <= x) { best = r; } if (best == -1) { return; } int l1 = sl - 1, r1 = best; while (r1 - l1 > 1) { int m = (l1 + r1) / 2; if (calc(m) <= x) { r1 = m; } else { l1 = m; } } for (int i = r1; i <= best; ++i) { ans[i] = 1; } l1 = best, r1 = sr; while (r1 - l1 > 1) { int m = (l1 + r1) / 2; if (calc(m) <= x) { l1 = m; } else { r1 = m; } } for (int i = best; i <= l1; ++i) { ans[i] = 1; } }; get(0, ind, calc); get(ind, n, calc); return ans; return ans; } void solve() { int n; cin >> n; vector<int> a(n * 2); for (auto &x : a) { cin >> x; } vector<int> b(n); for (auto &x : b) { cin >> x; } vector<int> c(n); for (auto &x : c) { cin >> x; } sort(all(b)); sort(all(c)); vector<int> a_(a.size()); for (int i = 0; i < a.size(); ++i) { a_[i] = a[(i + n) % a.size()]; } int l = -1, r = 1e9 + 1; while (r - l > 1) { int m = (l + r) / 2; vector<int> ansB = solve(a, b, m); vector<int> ansC = solve(a, c, m); vector<int> ansB_ = solve(a_, c, m); vector<int> ansC_ = solve(a_, b, m); bool ok = false; for (int i = 0; i < n; ++i) { if (ansB[i] && ansB_[i]) { ok = true; break; } if (ansC[i] && ansC_[i]) { ok = true; break; } } if (ok) { r = m; } else { l = m; } } cout << r << endl; } signed main() { #ifdef LOCAL freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #else ios::sync_with_stdio(false); cin.tie(0); #endif int t = 1; // cin >> t; while (t--) { solve(); } }