CF1805F1 Survival of the Weakest (easy version)

这是该问题的简单版本。它与困难版本的区别仅在于 $ n $ 的约束条件。只有同时锁定两个版本时，你才能进行 hack。 设 $ a_1, a_2, \ldots, a_n $ 是一个非负整数数组。定义 $ F(a_1, a_2, \ldots, a_n) $ 为将所有形如 $ a_i + a_j $（其中 $ 1 \le i < j \le n $）的和中最小的 $ n-1 $ 个数按非递减顺序排列后得到的数组。换句话说，$ F(a_1, a_2, \ldots, a_n) $ 是所有可能的数对之和中最小的 $ n-1 $ 个，按非递减顺序排列。例如，$ F(1, 2, 5, 7) = [1 + 2, 1 + 5, 2 + 5] = [3, 6, 7] $。 现给定一个非负整数数组 $ a_1, a_2, \ldots, a_n $，请你求出数组 $ \underbrace{F(F(F\ldots F}_{n-1}(a_1, a_2, \ldots, a_n)\ldots)) $ 的唯一元素。由于答案可能很大，请输出其对 $ 10^9+7 $ 取模的结果。

第一行包含一个整数 $ n $（$ 2 \le n \le 3000 $）——初始数组的长度。 第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $（$ 0 \le a_i \le 10^9 $）——数组元素。

输出一个整数，表示最终结果对 $ 10^9 + 7 $ 取模后的值。

在第一个测试样例中，数组的变化过程如下：$ [1, 2, 4, 5, 6] \to [3, 5, 6, 6] \to [8, 9, 9] \to [17, 17] \to [34] $。最终数组中唯一的元素为 $ 34 $。 在第二个测试样例中，$ F(a_1, a_2, \ldots, a_n) $ 为 $ [2, 2, 2, 8, 8, 8, 8, 8] $。该数组由 $ 3 $ 个 $ 1 + 1 $ 和 $ 5 $ 个 $ 1 + 7 $ 组成。 在第四个测试样例中，数组的变化过程如下：$ [10^9, 10^9, 777] \to [10^9+777, 10^9+777] \to [2 \cdot 10^9 + 1554] $。$ 2 \cdot 10^9 + 1554 $ 对 $ 10^9+7 $ 取模等于 $ 1540 $。 由 ChatGPT 4.1 翻译