← 返回题目列表

Codeforces · 1805/F1

F1. 弱者生存(简单版)

中文机器翻译题面 查看原题

这是问题的简单版本。它与困难的区别仅在于对 $$$n$$$ 的限制。只有锁定两个版本才可以进行黑客攻击。

设 $$$a_1, a_2, \ldots, a_n$$$ 为非负整数数组。令 $$$F(a_1, a_2, \ldots, a_n)$$$ 为在 $$$n - 1$$$ 形式的非降序数组中排序的最小数 $$$a_i + a_j$$$,其中 $$$1 \le i < j \le n$$$。换句话说,$$$F(a_1, a_2, \ldots, a_n)$$$ 是在 $$$n - 1$$$ 数组中所有可能的元素对的最小总和的非降序数组 $$$a_1, a_2, \ldots, a_n$$$ 中排序的。例如,$$$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

5
1 2 4 5 6

输出 #1

34

输入 #2

9
1 1 1 7 7 7 9 9 9

输出 #2

256

输入 #3

7
1 7 9 2 0 0 9

输出 #3

20

输入#4

3
1000000000 1000000000 777

输出#4

1540

注意

在第一个测试中,数组转换如下: $$$[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$$$。