题目描述

小A有一个包含N个正整数的序列 $A = {A_1, A_2, \dots, A_N}$，序列A恰好包含 $N/2$ 对不同的正整数。形式化地，对于任意 $1 \le i \le N$，存在唯一一个 $j$ 满足 $1 \le j \le N, i \neq j, A_i = A_j$。

小A希望每对相同的数字在序列中相邻，每次操作可以选择任意 $i\ (1 \le i \le N)$，将第 $i$ 个数字移动到任意位置，花费的体力等于该数字的值。

例如，序列 $A = {1,2,1,3,2,3}$，可以选择 $i=2$ 将 $A_2=2$ 移动到 $A_3=1$ 后面，序列变为 ${1,1,2,3,2,3}$，耗费2点体力；也可以选择 $i=3$ 将 $A_3=1$ 移动到 $A_2=2$ 前面，序列同样变为 ${1,1,2,3,2,3}$，花费1点体力。

小A可以执行任意次操作，要求每次操作花费的体力都不超过 $x$，求最小的 $x$。数据保证至少需要执行一次操作。

输入格式

第一行一个正整数 $N$，代表序列长度，保证 $N$ 为偶数。 第二行包含 $N$ 个正整数 $A_1, A_2, \dots, A_N$，代表序列 $A$，每个数恰好出现两次。

输出格式

输出一行，代表满足要求的 $x$ 的最小值。

样例

输入样例

6
1 2 1 3 2 3

输出样例

2

数据范围

• 对于40%的测试点，保证 $1 \le N, A_i \le 100$。
• 对于所有测试点，保证 $1 \le N, A_i \le 10^5$。