#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; bool way; vector<int> now(n); auto calc = [&](int i) { merge(a.begin() + i, a.begin() + n, a.rbegin() + (n - i), a.rbegin() + n, now.begin()); int ans = 0; for (int j = 0; j < n; ++j) { ans = max(ans, abs(now[j] - b[j])); } for (int j = 0; j < n; ++j) { if (abs(now[j] - b[j]) == ans) { if (now[j] > b[j]) { way = true; } else { way = false; } } } 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; } } // for (int i = 0; i < n; ++i) { // cout << calc(i) << ' '; // } // cout << endl; // cout << ind << endl; vector<int> ans(n, 0); auto get = [&](int l, int r, bool run, auto &&calc) { if (r < l) { return; } int sl = l, sr = r; while (r - l > 2) { int m1 = (l * 2 + r) / 3; int m2 = (l + 2 * r) / 3; int cm1 = calc(m1); int cm2 = calc(m2); if (cm1 < cm2 || (cm1 == cm2 && (way != run))) { 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 + 1; 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 - 1, false, calc); get(ind, n - 1, true, calc); 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()]; a_[i] = ((int)1e9) - a_[i]; } vector<int> b_ = b; vector<int> c_ = c; for (auto &x : b_) { x = ((int)1e9) - x; } for (auto &x : c_) { x = ((int)1e9) - x; } reverse(all(b_)); reverse(all(c_)); int l = -1, r = 1e9 + 1; while (r - l > 1) { int m = (l + r) / 2; // m = 3; 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); // for (auto &x : ansB) { // cout << x << ' '; // } // cout << endl; // for (auto &x : ansC) { // cout << x << ' '; // } // cout << endl; // for (auto &x : ansB_) { // cout << x << ' '; // } // cout << endl; // for (auto &x : ansC_) { // cout << x << ' '; // } // cout << endl; 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; } // break; } 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(); } }