题目描述

Carol 有两个长为 $n$ 的序列 $a,b$，而且她喜欢极差小的序列。由于她更喜欢 $a$，所以她只在乎 $a$ 的极差，即 $a$ 的最大值与最小值的差。

Carol 可以对序列进行操作。每次操作她可以选择一个 $i$，将 $a_i$ 和 $b_i$ 的值交换。

由于 Carol 是 Crazy Carol，所以她可以不做操作，也可以做任意多次操作。她想知道她最小可以将 $a$ 的极差降低到多少。

输入格式

第一行一个正整数 $n$，表示序列长度。

第二行共 $n$ 个正整数，第 $i$ 个整数表示 $a_i$ 的值。

第三行共 $n$ 个正整数，第 $i$ 个整数表示 $b_i$ 的值。

输出格式

一行一个整数，表示序列 $a$ 的最小极差。

3
1 5 3
2 3 1

1

数据范围

• 对于 $30\%$ 的数据：$n \leq 15$；

• 对于 $60\%$ 的数据：$n \leq 10^3$；

• 对于 $100\%$ 的数据：$n \leq 2 \times 10^5$。

• 对于所有数据，$1 \leq n \leq 2\times 10^5$，$1 \leq a_i, b_i \leq 10^9$。