29821번 - 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 in order (they must visit event $1$, then event $2$, then event $3$, \dots then event $n$).

Find the minimum 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.

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.