巴斯市是一个著名的奥林匹克训练基地，吸引了当地、全国乃至国际的队伍前来训练。然而，即使是最好的健身房也难免犯下大忌……哑铃被放错了位置。

所有的哑铃对在两个架子上摆放得杂乱无章，甚至有些哑铃对被拆分到了不同的行中。最初，每一行都有相同数量的哑铃，但由于这是一个资金充足的专业健身房，每一行的两端都有无限的空间来放置额外的重量。

要移动一个哑铃，你可以将其滚动到同一行中相邻的空位，几乎不费吹灰之力；或者你可以将其拿起并移动到另一个空位，这需要消耗与哑铃重量成正比的体力。对于每一对哑铃，两个哑铃的重量相同。

为了将相同的重量放在一起，你需要能够举起的最重哑铃的重量是多少？注意，重新排列后，每一行最终可能拥有不同数量的哑铃；这是允许的。

输入格式

输入包含： 一行包含整数 $n$ ($1 \le n \le 10^6$)，表示哑铃对的数量； 两行，每行包含 $n$ 个整数 $w_1 \dots w_n$ ($1 \le w_i \le 10^9$)，其中 $w_i$ 表示该行从左往右第 $i$ 个哑铃的质量。

输入中的每个重量恰好出现两次。

输出格式

输出为了使所有物品都能配对，同时保持所举起的最大重量尽可能小，所必须移动的最重哑铃的重量。

样例

输入 1

5
2 1 8 2 8
9 9 4 1 4

输出 1

2

输入 2

8
7 7 15 15 2 2 4 4
5 5 3 3 9 9 1 1

输出 2

0

Figure 1. 哑铃架上的哑铃摆放情况