問題文

それぞれ長さが $N$ の整数列 $A=(A_1,A_2,\ldots,A_N),B=(B_1,B_2,\ldots,B_N)$ が与えられます。ここで、 $A,B$ の各要素は偶数です。

また、長さが $N$ の整数列 $C=(C_1,C_2,\ldots,C_N)$ があり、$C_i (1\leq i \leq N)$ の値は $A_i,B_i,\frac{A_i+B_i}{2}$ のいずれかであることが分かっています。

$C$ の要素の最大値を $\max(C)$、最小値を $\min(C)$ とします。 $\max(C)-\min(C)$ の値としてあり得る値の最小値を求めてください。

入力

$N$
$A_1\ A_2\ \ldots\ A_N$
$B_1\ B_2\ \ldots\ B_N$

• $1\le N\le 2×10^5$
• $0\le A_i,B_i\le 10^9$
• $A_i,B_i$ は偶数
• 入力は全て整数

出力

$\max(C)-\min(C)$ の値としてあり得る値の最小値を出力してください。

サンプル

3
6 2 12
6 10 2

1

4   
4 6 4 2
4 6 4 2

4

3
4 10 20
16 2 0

0