#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 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, pii &best) { 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) { if (ans < abs(now[j] - b[j])) { ans = abs(now[j] - b[j]); way = (now[j] > b[j]); } } return ans; }; int ind = n; for (int i = 0; i < n; ++i) { if (a[i] >= a[n + i]) { ind = i; break; } } vector<int> ans(n, 0); auto get = [&](int l, int r, bool run, auto &&calc) { if (r < l) { return; } int sl = l, sr = r; int bestnow; if ((run == false && best.f == -1)) { 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 cl = calc(l); int clr = calc((l + r) / 2); int cr = calc(r); if (cl <= clr && cl <= cr) { best.f = l; } else if (clr <= cr) { best.f = (l + r) / 2; } else { best.f = r; } bestnow = best.f; } if ((run == true && best.s == -1)) { 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 cl = calc(l); int clr = calc((l + r) / 2); int cr = calc(r); if (cl <= clr && cl <= cr) { best.s = l; } else if (clr <= cr) { best.s = (l + r) / 2; } else { best.s = r; } } if (!run) { bestnow = best.f; } else { bestnow = best.s; } if (calc(bestnow) > x) { return; } int l1 = sl - 1, r1 = bestnow; while (r1 - l1 > 1) { int m = (l1 + r1) / 2; if (calc(m) <= x) { r1 = m; } else { l1 = m; } } for (int i = r1; i <= bestnow; ++i) { ans[i] = 1; } l1 = bestnow, r1 = sr + 1; while (r1 - l1 > 1) { int m = (l1 + r1) / 2; if (calc(m) <= x) { l1 = m; } else { r1 = m; } } for (int i = bestnow; 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_)); pii B[4]; for (int i = 0; i < 4; ++i) { B[i] = mp(-1, -1); } int l = -1, r = 1e9 + 1; while (r - l > 1) { int m = (l + r) / 2; // m = 3; vector<int> ansB = solve(a, b, m, B[0]); vector<int> ansB_ = solve(a_, c_, m, B[1]); bool ok = false; for (int i = 0; i < n; ++i) { if (ansB[i] && ansB_[i]) { ok = true; break; } } if (!ok) { vector<int> ansC = solve(a, c, m, B[2]); vector<int> ansC_ = solve(a_, b_, m, B[3]); for (int i = 0; i < n; ++i) { 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(); } }