CCF GESP 2025年12月认证 C++ 5级

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

小 A 希望每对相同的数字在序列中相邻，为了实现这一目的，小 A 每次操作会选择任意$i(1≤i≤N)$，将当前序列的第 $i$ 个数字移动到任意位置，并花费对应数字的体力。

例如，假设序列 $A=\{{1,2,1,3,2,3}\}$，小 A 可以选择 $i=2$，将 $A_2=2$ 移动到 $A_3=1$ 的后面，此时序列变为 $\{1,1,2,3,2,3\}$，耗费 $2$ 点体力。小 A 也可以选择 $i=3$，将 $A_3=1$ 移动到 $A_2=2$ 的前面，此时序列变为 $\{1,1,2,3,2,3\}$，花费 $1$ 点体力。

小 A 可以执行任意次操作，但他希望自己每次花费的体力尽可能小。小 A 希望你能帮他计算出一个最小的 $x$，使得他能够在每次花费的体力均不超过 $x$ 的情况下令每对相同的数字在序列中相邻。

小 A 有一个包含 $N$ 个正整数的序列 $A=\{{A_1,A_2.....A_N}\}$。小 A 每次可以花费 1 个金币执行以下任意一种操作：

• 选择序列中一个正整数 $A_i(1≤i≤N)$，将 $A_i$ 变为 $A_i \times P$，$P$ 为任意质数；
• 选择序列中一个正整数 $A_i(1≤i≤N)$，将 $A_i$ 变为 $\frac{A_i}{P}$，$P$ 为任意质数，要求 $A_i$ 能被 $P$ 整除。

小 A 想请你帮他计算出令序列中所有整数都相同，最少需要花费多少金币。