Description

Alice and Bob are driving on a very long road that stretches from points $-10^9$ to $10^9$. Alice starts at point $A$ while Bob starts at point $B$. There are $n$ events to visit, where event $i$ is at position $t_i$. Either Alice or Bob must visit each event, but they must be visited $\textbf{in order}$ (they must visit event $1$, then event $2$, then event $3$, $\dots$ then event $n$).

Find the minimum $\textbf{total}$ distance Alice and Bob can drive to visit all events.

Input Format

The first line contains a single integer $n$ ($1\le n\le3\cdot10^5$) --- the number of events.

The second line contains two integers $A$ and $B$ ($-10^9\le A,B\le10^9$) --- Alice and Bob's starting points.

The third line contains $n$ integers $t_1,t_2,\dots,t_n$ ($-10^9\le t_i\le10^9$) --- the locations of events either Alice or Bob must get to.

Output Format

Output an integer --- the minimum total distance Alice and Bob drive.

5
2 3
5 1 4 4 7

7

6
540 152
450 600 532 496 325 336

526

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

1699

Hint

Note

In the first example:

• Bob moves from position $3$ to position $5$ to attend event $1$, driving $2$ units.
• Alice moves from position $2$ to position $1$ to attend event $2$, driving $1$ unit.
• Bob moves from position $5$ to position $4$ for event $3$, driving $1$ unit.
• Bob stays at position $4$, attending event $4$, driving $0$ units.
• Bob moves from position $4$ to position $7$ for event $5$, driving $3$ units.

The total distance travelled is $2+1+1+0+3=7$.

In the second example, Alice visits all events.

Scoring

Subtask 1 ($5$ points) $|t_i|,|A|\le1000,B=10^9$

Subtask 2 ($8$ points) $n\le20$

Subtask 3 ($19$ points) $n\le3000$

Subtask 4 ($12$ points) $n\le10^5,|t_i|,|A|,|B|\le100$

Subtask 5 ($43$ points) $|t_i|,|A|,|B|\le2\cdot10^5$

Subtask 6 ($13$ points) No additional constraints