P15292 [MCO 2023] Two Pointers (hard version)

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.

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 an integer --- the minimum total distance Alice and Bob drive.

### 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