题目描述

Alice 和 Bob 正在一条从 $-10^9$ 到 $10^9$ 的漫长公路上行驶。Alice 的起始位置为 $A$，Bob 的起始位置为 $B$。共有 $n$ 个事件需要访问，第 $i$ 个事件位于位置 $t_i$。每个事件必须由 Alice 或 Bob 中的一人访问，且必须按顺序访问（即必须先访问事件 $1$，然后是事件 $2$，接着是事件 $3$，以此类推，直到事件 $n$）。

求 Alice 和 Bob 访问所有事件所行驶的总距离的最小值。

输入格式

第一行包含一个整数 $n$ ($1\le n\le3\cdot10^5$)，表示事件的数量。

第二行包含两个整数 $A$ 和 $B$ ($-10^9\le A,B\le10^9$)，表示 Alice 和 Bob 的起始位置。

第三行包含 $n$ 个整数 $t_1,t_2,\dots,t_n$ ($-10^9\le t_i\le10^9$)，表示 Alice 或 Bob 必须到达的事件位置。

输出格式

输出一个整数，表示 Alice 和 Bob 行驶的总距离的最小值。

子任务

子任务 1 ($5$ 分)：$|t_i|,|A|\le1000,B=10^9$

子任务 2 ($8$ 分)：$n\le20$

子任务 3 ($19$ 分)：$n\le3000$

子任务 4 ($12$ 分)：$n\le10^5,|t_i|,|A|,|B|\le100$

子任务 5 ($43$ 分)：$|t_i|,|A|,|B|\le2\cdot10^5$

子任务 6 ($13$ 分)：无额外限制

样例

输入 1

5
2 3
5 1 4 4 7

输出 1

7

输入 2

6
540 152
450 600 532 496 325 336

输出 2

526

输入 3

8
35 315
-406 -543 114 205 -840 161 540 -731

输出 3

1699

说明

在第一个样例中：

• Bob 从位置 $3$ 移动到位置 $5$ 参加事件 $1$，行驶 $2$ 个单位。
• Alice 从位置 $2$ 移动到位置 $1$ 参加事件 $2$，行驶 $1$ 个单位。
• Bob 从位置 $5$ 移动到位置 $4$ 参加事件 $3$，行驶 $1$ 个单位。
• Bob 停留在位置 $4$ 参加事件 $4$，行驶 $0$ 个单位。
• Bob 从位置 $4$ 移动到位置 $7$ 参加事件 $5$，行驶 $3$ 个单位。

总行驶距离为 $2+1+1+0+3=7$。

在第二个样例中，Alice 访问了所有事件。