C. 信仰崩塌

核心结论

这是一道构造题，我们只需要补一个数字到 $b$ 数组中，就能得到满足所有条件的 $a$ 数组。 补的数字可以直接计算得出，且构造方式固定、简单、合法。

---

题意公式回顾

原序列 $a$ 长度为 $2n+1$，必须满足：

$$a_1 = a_2 - a_3 + a_4 - a_5 + \dots + a_{2n} - a_{2n+1} $$

我们已知的是：$a$ 删去一个元素、打乱后得到 $b$（长度 $2n$）。

---

构造思路

步骤 1

把 $b$ 数组从大到小排序。

步骤 2

计算要补的数 $sum$（就是被删掉的那个数）：

$$sum = b_0 + b_1 + (b_2 - b_3) + (b_4 - b_5) + \dots $$

步骤 3

按下面格式输出最终 $a$ 数组（满足公式 + 互不相同）：

$$a = [\ b_0,\ sum,\ b_1,\ b_3,\ b_2,\ b_5,\ b_4,\ \dots \ ] $$

---

严格证明构造合法

1. 满足公式

按构造输出的 $a$ 满足：

$$a_1 = a_2 - a_3 + a_4 - a_5 + \dots + a_{2n} - a_{2n+1} $$

代入构造形式：

$$b_0 = sum - b_1 + b_2 - b_3 + \dots$$

而我们的 $sum$ 就是按这个等式算出来的，等式天然成立。

2. 所有数互不相同

• $sum$ 由最大的两个数相加再加减得到，一定严格大于 $b$ 中所有数。
• $b$ 中数本来就互不相同。
• 因此最终 $a$ 数组两两不同。

3. 数值范围合法

$sum \le 10^{18}$，完全满足题目要求。

---

复杂度

• 排序：$O(n\log n)$
• 计算：$O(n)$
• 总复杂度：$O(n\log n)$
  完全可以通过 $n \le 2\times 10^5$。

---

最终总结

1. 把 $b$ 从大到小排序
2. 算一个补数 $sum$
3. 按固定格式输出 $a$ 数组 就可以满足题目所有条件。