该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

星际联邦有一个长度为 $N$ 的战舰序列，其中每个能量级别都恰好出现两次。

指挥官希望经过若干次移动操作后，使得每一对相同能量级别的战舰在序列中都相邻。

一次移动操作的规则如下：

• 你可以选择当前序列中的任意一个元素；
• 把它移动到当前序列中的任意位置；
• 这次操作的代价等于这个元素本身的数值。

你可以进行任意多次操作，但希望“单次操作代价的最大值”尽可能小。

请你输出这个最小值。

输入格式

第一行一个偶数整数 $N$。

第二行 $N$ 个正整数，表示原序列。

输出格式

输出一个整数，表示最小可能的最大单次操作代价。

6
1 2 1 2 3 3

1

8
4 1 2 1 3 4 2 3

3

说明/提示

样例 1 解释：

把第三个数 1 移动到第一个数 1 的后面，序列就会变成 1 1 2 2 3 3。这次移动的代价为 $1$，因此答案不超过 $1$；显然不进行任何移动无法达成目标，所以答案就是 $1$。

样例 2 解释：

若限制单次移动代价不超过 $2$，则值为 $3$ 和 $4$ 的元素都不能动，保留下来的顺序是 4 3 4 3，无法让相同元素相邻；而当限制放宽到 $3$ 时，值为 $4$ 的两个元素已经天然可以视作固定相邻结构，其他元素可通过移动完成配对，因此答案为 $3$。

对于所有测试点，保证 $2 \le N \le 10^5$，$1 \le A_i \le 10^5$，且每个数恰好出现两次。