题目背景

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

题目描述

小 A 有一个包含 $N$ 个正整数的序列 $A={A_1,A_2,ldots,A_N}$，序列 $A$ 恰好包含 $N/2$ 对不同的正整数。形式化地，对于任意 $1 \le i\le N$，存在唯一一个 $j$ 满足 $1 \le j\le N$、$i e 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

数据范围与提示

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

样例中移动数值为 $2$ 的元素即可使一对 $1$ 相邻，并继续整理得到所有相同数字相邻，因此答案不超过 $2$；无法只移动花费不超过 $1$ 的数字完成目标。