P15136 [SWERC 2025] Billion Players Game

你正在关注 Billion Players Game 的世界锦标赛。共有 $10^9$ 名玩家参赛，你想预测你最喜欢的主播 Godflex 的最终排名 $p$。通过分析最近的比赛，你确信 $l \le p \le r$，但除此之外一无所知。 游戏内的庄家提供了 $n$ 个报价。在第 $i$ 个报价中，庄家给出了对 Godflex 最终排名的一个估计值 $a_i$。对于每个报价，你必须**恰好**选择以下行动之一： - 忽略该报价。 - 接受报价，并声称 $p \le a_i$。如果你正确，你将获得 $|p - a_i|$ 枚硬币；否则你将失去 $|p - a_i|$ 枚硬币。 - 接受报价，并声称 $p \ge a_i$。如果你正确，你将获得 $|p - a_i|$ 枚硬币；否则你将失去 $|p - a_i|$ 枚硬币。 在你决定如何处理所有报价后，实际的 Billion Players Game 开始进行。Godflex 获得一个在 $[l, r]$ 范围内的整数排名 $p$，随后所有报价被结算。 你的总得分是你**保证**能获得的硬币数，即对于所有可能的 $p \in [l, r]$，你获得的硬币数的**最小值**。请找出你能保证的**最大可能得分**。

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。接下来是每个测试用例的描述。 每个测试用例的第一行包含三个整数 $n, l, r$（$1 \le n \le 2 \cdot 10^5$，$1 \le l \le r \le 10^9$）—— 分别表示报价的数量以及 Godflex 最终排名的可能范围。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）—— 庄家在每个报价中对 Godflex 排名的估计值。 保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一行一个整数：你能保证的最大可能得分。

#### 样例 1 解释 在第一个测试用例中，只有一个报价。 - 如果你忽略该报价，你的得分为 $0$； - 如果你接受报价并声称 $p \le 3$，你的得分为 $-2$（当 $p = 5$ 时，你会损失 $|5 - 3| = 2$ 枚硬币）； - 如果你接受报价并声称 $p \ge 3$，你的得分为 $-2$（当 $p = 1$ 时，你会损失 $|1 - 3| = 2$ 枚硬币）。 因此最大可能得分为 $0$。 在第二个测试用例中，最优策略是接受报价并分别声称 $p \ge 50$ 和 $p \le 200$。由于 $p$ 必须为 $100$，你将获得 $|100 - 50| + |100 - 200| = 150$ 枚硬币。 翻译由 DeepSeek 完成