题意

定义一个操作 $F(a_1, a_2, \dots, a_n)$：取所有 $i<j$ 的和 $a_i+a_j$，排序后保留最小的 $n-1$ 个数，作为新数组。
重复应用 $F$ 共 $n-1$ 次，最终得到一个单元素数组。求这个元素的值，对 $10^9+7$ 取模。

---

关键观察

设当前数组为 $a_1 \le a_2 \le \dots \le a_n$（已排序）。

考虑所有两两和 $a_i + a_j$（$i<j$）。
最小的和显然是 $a_1 + a_2$。
第二小的可能是 $a_1 + a_3$ 或 $a_2 + a_2$（若允许 $i=j$ 则 $2a_2$，但这里 $i<j$ 不允许相同下标，所以 $a_2+a_2$ 不合法）。
实际上，最小的 $n-1$ 个和具有特殊结构。

---

核心结论

经过分析，每次变换后的数组元素可以表示为：

• 新数组的第一个元素是 $a_1 + a_2$
• 其余元素是 $a_i + a_1$（$i \ge 2$）的一些组合

更具体地，变换后的数组等价于：

$$[\,a_1+a_2,\; a_1+a_3,\; a_1+a_4,\; \dots,\; a_1+a_n\,] $$

但需要排序，且长度变为 $n-1$。实际上，这个序列已经单调不减（因为 $a_2 \le a_3 \le \dots$），所以就是这 $n-1$ 个数。

---

变换规律

设当前数组为 $b_1 \le b_2 \le \dots \le b_m$。
则下一次变换后的数组为：

$$[\,b_1+b_2,\; b_1+b_3,\; b_1+b_4,\; \dots,\; b_1+b_m\,] $$

即每个元素减去 $b_1$ 后，新数组为 $[b_2,\; b_3,\; \dots,\; b_m]$ 每个加上 $b_1$。

因此，我们可以用增量累加的方式模拟：

• 每次取出当前最小值 $x = a_0$
• 将答案 $ans$ 更新为 $(ans + x) \times 2 \pmod{MOD}$（因为每次变换后，最终结果都会受到 $x$ 的影响，且后续会累加）
• 然后从数组中移除 $a_0$，并将剩余所有元素减去 $x$（这相当于后续的 $a_i + x$ 变成 $a_i$）

---

算法步骤

$1$. 对数组排序。 $2$. 初始化答案 $ans = 0$。 $3$. 当 $n > 1$ 时：

• 取出最小值 $x = a[0]$
• $ans = (ans + x) \times 2 \pmod{MOD}$
• 将 $a[1..n-1]$ 每个元素减去 $x$
• 删除 $a[0]$（即把 $a[1..n-1]$ 左移一位）
• $n$ 减 1 $4$. 输出 $ans$（注意最后不需要再加 $a[0]$，因为最后一步已经包含在累加中）

---

正确性说明

每次变换相当于：新数组 = $[x + a_1, x + a_2, \dots, x + a_{n-1}]$，其中 $x$ 是原最小值。
最终结果可以通过递推得到：

$$\text{最终} = 2 \times (\text{最终结果的前一步} + x)$$

因此用递推累加即可。

---

示例验证

样例 1

输入：

5
1 2 4 5 6

排序后：$[1,2,4,5,6]$

• 第1步：$x=1$, $ans=(0+1)*2=2$, 数组变为 $[1,3,4,5]$
• 第2步：$x=1$, $ans=(2+1)*2=6$, 数组变为 $[2,3,4]$
• 第3步：$x=2$, $ans=(6+2)*2=16$, 数组变为 $[1,2]$
• 第4步：$x=1$, $ans=(16+1)*2=34$, 数组变为 $[1]$ 输出 $34$ ✅

样例 4

输入：

3
1000000000 1000000000 777

排序后：$[777, 10^9, 10^9]$

• 第1步：$x=777$, $ans=(0+777)*2=1554$, 数组变为 $[10^9-777, 10^9-777]$
• 第2步：$x=10^9-777$, $ans=(1554 + 10^9-777)*2$ 模 $10^9+7$
  计算：$1554 + (10^9-777) = 10^9 + 777$，乘 2 得 $2\times 10^9 + 1554$，模 $10^9+7$ 得 $1540$ ✅

---

完整代码

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;

int main() {
    int n;
    cin >> n;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a.begin(), a.end());

    long long ans = 0;
    while (n > 1) {
        long long x = a[0];
        ans = (ans + x) * 2 % MOD;
        for (int i = 1; i < n; i++) a[i] -= x;
        for (int i = 1; i < n; i++) a[i-1] = a[i];
        n--;
    }
    cout << ans << "\n";
    return 0;
}

---

复杂度

• 每次循环 $O(n)$ 平移数组，总复杂度 $O(n^2)$，$n \le 3000$ 可过。
• 空间 $O(n)$。