说明

爱丽丝和鲍勃正在一条从 $-10^9$ 延伸至 $10^9$ 的极长道路上参观城市。爱丽丝从点 $A$ 出发，鲍勃从点 $B$ 出发。

共有 $n$ 个城市需要参观，第 $i$ 个城市位于点 $t_i$。每个城市必须被爱丽丝或鲍勃至少参观一次，并且他们可以按 任意顺序 参观这些城市。

爱丽丝和鲍勃 总共 需要移动的最小距离是多少？

输入格式

每个测试点包含多个测试用例。第一行包含一个整数 $T$ （$1 \le T \le 100$），表示测试用例的数量。每个测试用例格式如下：

第一行包含三个以空格分隔的整数 $n$、$A$ 和 $B$ （$1 \le n \le 2 \cdot 10^5$， $-10^9 \le A, B \le 10^9$）—— 分别表示城市的数量、爱丽丝的起始位置和鲍勃的起始位置。

第二行包含 $n$ 个以空格分隔的整数 $t_1, t_2, \ldots, t_n$ （$-10^9 \le t_i \le 10^9$）—— 各个城市的位置。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，在单独的一行输出答案。

输出爱丽丝和鲍勃为了参观所有城市必须移动的最小总距离。

4
7 -6 10
-15 -1 12 8 11 -6 0
2 -1000000000 -1000000000
1000000000 -1000000000
1 4 6
1
4 727 137
39 852 201 696

24
2000000000
3
413

提示

注释

:::align{center} :::

在第一个测试用例中：共有 $7$ 个城市。爱丽丝从坐标 $-6$ 出发，鲍勃从点 $10$ 出发。

一种参观所有城市的最优方案如下（$i \xrightarrow{x} j$ 表示从 $i$ 到 $j$，行驶距离 $x$）：

• 爱丽丝按顺序参观的城市： $A \xrightarrow{0} \text{城市 }6 \xrightarrow{9} \text{城市 }1$。
• 鲍勃按顺序参观的城市： $B \xrightarrow{1} \text{城市 }5 \xrightarrow{1} \text{城市 }3 \xrightarrow{4} \text{城市 }4 \xrightarrow{8} \text{城市 }7 \xrightarrow{1} \text{城市 }2$。

爱丽丝总共行驶了 $0 + 9 = 9$ 距离，鲍勃总共行驶了 $1 + 1 + 4 + 8 + 1 = 15$ 距离。爱丽丝和鲍勃行驶的总距离为 $9 + 15 = 24$。可以证明不存在总距离小于 $24$ 的方案，因此答案为 $24$。

在第二个测试用例中，爱丽丝和鲍勃都已经位于城市 $2$。鲍勃可以先参观城市 $2$，再参观城市 $1$，总共行驶 $2,000,000,000$ 距离。注意，爱丽丝可以选择什么都不做。

在第三个测试用例中，爱丽丝可以参观唯一的一座城市，从点 $4$ 行驶到点 $1$，距离为 $3$。鲍勃什么都不做。

计分

子任务 1 （$16$ 分）： $n \le 20$， $-10^6 \le A, B, t_i \le 10^6$

子任务 2 （$36$ 分）： $n \le 5000$， $-10^6 \le A, B, t_i \le 10^6$

子任务 3 （$21$ 分）： $n \le 5000$

子任务 4 （$27$ 分）： 无额外限制

翻译由 DeepSeek 完成