import sys input = sys.stdin.readline from bisect import bisect_left mod = 998244353 class SparseTable(): def __init__(self, A, STfunc): # A: 処理したい数列 self.N = len(A) self.K = self.N.bit_length() - 1 self.table = [0] * (self.N * (self.K + 1)) self.STfunc = STfunc for i, a in enumerate(A): self.table[i] = a for k in range(1, self.K + 1): for i in range(self.N): j = i + (1 << (k-1)) if j <= self.N-1: self.table[i + k * self.N] = STfunc(self.table[i + (k-1) * self.N], self.table[j + (k-1) * self.N]) def query(self, l, r): l -= 1 r -= 1 # [l, r)の最小値を求める k = (r-l).bit_length() - 1 return self.STfunc(self.table[l + k * self.N], self.table[r - (1 << k) + k * self.N]) class SegmentTree: def __init__(self, A, initialize=True, segfunc=min, ident=2000000000): self.N = len(A) self.LV = (self.N - 1).bit_length() self.N0 = 1 << self.LV self.segfunc = segfunc self.ident = ident if initialize: self.data = [self.ident] * self.N0 + A + [self.ident] * (self.N0 - self.N) for i in range(self.N0 - 1, 0, -1): self.data[i] = segfunc(self.data[i * 2], self.data[i * 2 + 1]) else: self.data = [self.ident] * (self.N0 * 2) def update(self, i, x): i += self.N0 - 1 self.data[i] = x for _ in range(self.LV): i >>= 1 self.data[i] = self.segfunc(self.data[i * 2], self.data[i * 2 + 1]) def get(self, i): return self.data[i + self.N0 - 1] # open interval [l, r) def query(self, l, r): l += self.N0 - 1 r += self.N0 - 1 ret_l = self.ident ret_r = self.ident while l < r: if l & 1: ret_l = self.segfunc(ret_l, self.data[l]) l += 1 if r & 1: ret_r = self.segfunc(self.data[r - 1], ret_r) r -= 1 l >>= 1 r >>= 1 return self.segfunc(ret_l, ret_r) # return smallest i(l <= i < r) s.t. check(A[i]) == True def binsearch(self, l, r, check): if not check(self.query(l, r)): return r l += self.N0 - 1 val = self.ident while True: if check(self.segfunc(val, self.data[l])): break if l & 1: val = self.segfunc(val, self.data[l]) l += 1 l >>= 1 while l < self.N0: newval = self.segfunc(val, self.data[l * 2]) if not check(newval): val = newval l = (l << 1) + 1 else: l <<= 1 return l - self.N0 + 1 N = int(input()) A_ori = list(map(int, input().split())) B_ori = list(map(int, input().split())) X = [] for a, b in zip(A_ori, B_ori): if a > b: a, b = b, a X.append((a, b, (a + b) // 2)) X.sort(key=lambda x: x[2]) A = [] B = [] AB = [] val = set() for a, b, ab in X: A.append(a) B.append(b) AB.append(ab) val.add(a) val.add(b) val.add(ab) ST_A_min = SparseTable(A, min) ST_A_max = SparseTable(A, max) ST_B_min = SegmentTree(B) ST_B_max = SegmentTree(B, initialize=True, segfunc=max, ident=-2000000000) ans = min(max(A) - min(A), max(B) - min(B)) for v in sorted(list(val)): i = bisect_left(AB, v) if i != 0: mi_B = ST_B_min.query(1, i + 1) ma_B = ST_B_max.query(1, i + 1) if mi_B < v: continue else: ma_B = -1 mi_B = 10 ** 10 ok = max(ma_B, AB[-1]) ng = min(v, ma_B) - 1 if (ng + 1) - v >= ans: continue mid = (ok + ng) // 2 while ok - ng > 1: r = bisect_left(AB, mid + 1) flg = 1 if r != N: mi_A = ST_A_min.query(r+1, N+1) ma_A = ST_A_max.query(r+1, N+1) if mi_A < v or ma_A > mid: flg = 0 if flg: ok = mid else: ng = mid mid = (ok + ng) // 2 ans = min(ans, ok - v) print(ans)