AT_arc073_d [ARC073F] Many Moves

[problemUrl]: https://atcoder.jp/contests/arc073/tasks/arc073_d $ N $ 個のマスが一列に並んでいます。マスには順に $ 1,\ 2,\ ...,\ N $ と番号を振ってあるものとします。 あなたはコマを $ 2 $ つ持っており、最初の時点ではマス $ A $, $ B $ においてあります。 以下のクエリが$ Q $ 個与えられるので、順番に処理します。 - $ x_i $ が与えられる。$ 2 $ つのコマのどちらかをマス $ x_i $ に移動させる。どちらを移動させるかは好きに選んで良い。 ただし、コマは $ 1 $ マス分動くのに $ 1 $ 秒の時間を必要とします。 つまり、マス $ X $ のコマをマス $ Y $ に動かすには $ |X-Y| $ 秒必要です。 あなたの目的は、出来る限り速く全てのクエリを処理することです。 なお、クエリ以外でのコマの移動は許されません。 また、クエリの順番を並び替えたり、コマを $ 2 $ 個同時に動かしたりすることも許されません。 ただし、$ 2 $ 個のコマが同時に同じマスにいることは許されます。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ A $ $ B $ $ x_1 $ $ x_2 $ ... $ x_Q $

全てのクエリを処理するのにかかる最小の時間を $ X $ 秒として、$ X $ を出力する。

### 制約 - $ 1\ ≦\ N,\ Q\ ≦\ 200,000 $ - $ 1\ ≦\ A,\ B\ ≦\ N $ - $ 1\ ≦\ x_i\ ≦\ N $ ### Sample Explanation 1 \- マス $ 1 $ のコマをマス $ 3 $ に動かす - マス $ 8 $ のコマをマス $ 5 $ に動かす - マス $ 3 $ のコマをマス $ 1 $ に動かす この通りにコマを動かすと $ 7 $ 秒で全てのクエリを処理できます。 ### Sample Explanation 2 最初に動かすべきはマス $ 9 $ のコマです。 ### Sample Explanation 3 最初に動かすべきはマス $ 1 $ のコマです。