您正在关注十亿玩家游戏世界冠军赛。有 $$$10^9$$$ 玩家参加比赛,您想预测您最喜欢的主播 Godflex 的最终排名 $$$p$$$。分析最近的比赛后,您确定 $$$l \leq p \leq r$$$,但您不知道其他任何事情。
游戏内博彩公司提供了 $$$n$$$ 优惠。在第 $$$i$$$ 报价中,博彩公司建议对 Godflex 的最终排名进行 $$$a_i$$$ 估计。对于每个优惠,您必须准确选择以下操作之一:
- 忽略该提议。
- 接受报价,声明 $$$p \leq a_i$$$。如果你是对的,你将赚取 $$$|p-a_i|$$$ 机器人币;否则你会损失 $$$|p-a_i|$$$ 机器人币。
- 接受报价,声明 $$$p \geq a_i$$$。如果你是对的,你将赚取 $$$|p-a_i|$$$ 机器人币;否则你会损失 $$$|p-a_i|$$$ 机器人币。
在您决定如何处理所有优惠后,就会开始真正的十亿玩家游戏。 Godflex 在 $$$[l, r]$$$ 中获得 $$$p$$$ 仓位,然后结算所有报价。
您的总分是您保证获得的机器人币数量,即您在 $$$[l, r]$$$ 中 $$$p$$$ 的所有可能值中获得的最小机器人币数量。找出你能保证的最高可能分数。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含三个整数 $$$n$$$, $$$l$$$, $$$r$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq l \leq r \leq 10^9$$$) — 报价数量和 Godflex 最终排名的可能范围。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) - 博彩公司对 Godflex 在每个报价中的排名的估计。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一行包含一个整数:您可以保证的最大可能分数。
示例
输入复制
41 1 532 100 10050 2005 1 105 7 3 9 15 6 109 3 1 7 5
输出复制
01501213
注意
在第一个测试用例中,只有一个报价。
- 如果您忽略该优惠,您的分数为 $$$0$$$;
- 如果您接受声称 $$$p \leq 3$$$ 的报价,您的分数为 $$$-2$$$(当 $$$p = 5$$$ 时达到,这会让您损失 $$$|5-3| = 2$$$ 机器人币);
- 如果您接受声称 $$$p \geq 3$$$ 的报价,您的分数为 $$$-2$$$(当 $$$p = 1$$$ 时达到,这会让您损失 $$$|1-3| = 2$$$ 机器人币)。
因此最大可能得分为 $$$0$$$。
在第二个测试用例中,最好接受声称 $$$p \geq 50$$$ 和 $$$p \leq 200$$$ 的报价。由于 $$$p$$$ 必须为 $$$100$$$,因此您将获得 $$$|100-50| + |100-200| = 150$$$ 机器人币。