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

题目背景

2025 年 12 月 GESP C++ 五级编程第 1 题

题目描述

小 A 有一个包含 $N$ 个正整数的序列 $A = \{A_1, A_2, \ldots, A_N\}$，序列 $A$ 恰好包含 $\frac{N}{2}$ 对不同的正整数。也就是说，对于任意 $1 \le i \le N$，存在唯一一个 $j$ 满足 $1 \le j \le N$、$i \ne j$ 且 $A_i = A_j$。

小 A 希望每对相同的数字在序列中相邻。每次操作可以选择任意位置的一个数字，将它移动到任意位置，并花费等于该数字的体力。

请计算一个最小的 $x$，使得小 A 能够在每次花费的体力均不超过 $x$ 的情况下，令每对相同的数字在序列中相邻。数据保证小 A 至少需要执行一次操作。

输入格式

第一行输入一个正整数 $N$，保证 $N$ 为偶数。

第二行输入 $N$ 个正整数 $A_1, A_2, \ldots, A_N$。

输出格式

输出一行一个整数，表示满足要求的 $x$ 的最小值。

样例

6
1 2 1 3 2 3

2

样例解释

序列为 $[1, 2, 1, 3, 2, 3]$。

一种可行方案为：

1. 将位置 $5$ 的数字 $2$ 移动到末尾，花费 $2$，序列变为 $[1, 2, 1, 3, 3, 2]$；
2. 将位置 $2$ 的数字 $2$ 移动到位置 $5$，花费 $2$，序列变为 $[1, 1, 3, 3, 2, 2]$。

此时所有相同数字均相邻，每次操作的最大花费为 $2$。无法只使用花费不超过 $1$ 的操作完成目标，因为至少需要移动一个数字 $2$ 或更大的数字来调整相对位置。因此最小 $x$ 为 $2$。

数据范围与提示

• 对于 $40\%$ 的测试点：$1 \le N, A_i \le 100$；
• 对于所有测试点：$1 \le N, A_i \le 10^5$，$N$ 为偶数。