P15292 [MCO 2023] Two Pointers (hard version)

爱丽丝和鲍勃在一条从 $-10^9$ 延伸至 $10^9$ 的极长道路上驾车。爱丽丝从点 $A$ 出发，鲍勃从点 $B$ 出发。共有 $n$ 个事件需要前往，其中第 $i$ 个事件位于位置 $t_i$。每个事件必须由爱丽丝或鲍勃中的一人前往，并且他们必须 **按顺序** 依次访问（必须先访问事件 $1$，再访问事件 $2$，再访问事件 $3$，……，最后访问事件 $n$）。 求爱丽丝和鲍勃驾车前往所有事件所需的最小 **总** 距离。

第一行包含一个整数 $n$ （$1\le n\le3\cdot10^5$）—— 事件的数量。 第二行包含两个整数 $A$ 和 $B$ （$-10^9\le A,B\le10^9$）—— 爱丽丝和鲍勃的起点。 第三行包含 $n$ 个整数 $t_1,t_2,\dots,t_n$ （$-10^9\le t_i\le10^9$）—— 爱丽丝或鲍勃必须前往的事件位置。

输出一个整数 —— 爱丽丝和鲍勃驾车的最小总距离。

#### 注释 在第一个样例中： - 鲍勃从位置 $3$ 移动到位置 $5$ 参加事件 $1$，行驶 $2$ 个单位。 - 爱丽丝从位置 $2$ 移动到位置 $1$ 参加事件 $2$，行驶 $1$ 个单位。 - 鲍勃从位置 $5$ 移动到位置 $4$ 参加事件 $3$，行驶 $1$ 个单位。 - 鲍勃停留在位置 $4$，参加事件 $4$，行驶 $0$ 个单位。 - 鲍勃从位置 $4$ 移动到位置 $7$ 参加事件 $5$，行驶 $3$ 个单位。 总行驶距离为 $2+1+1+0+3=7$。 在第二个样例中，爱丽丝参加了所有事件。 #### 计分 **子任务 1** （$5$ 分） $|t_i|, |A| \le 1000$， $B = 10^9$ **子任务 2** （$8$ 分） $n \le 20$ **子任务 3** （$19$ 分） $n \le 3000$ **子任务 4** （$12$ 分） $n \le 10^5$， $|t_i|, |A|, |B| \le 100$ **子任务 5** （$43$ 分） $|t_i|, |A|, |B| \le 2 \cdot 10^5$ **子任务 6** （$13$ 分） 无额外限制 翻译由 DeepSeek 完成