AtCoder Regular Contest 073

F - Many Moves


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

Score : 900 points

Problem Statement

There are N squares in a row. The squares are numbered 1, 2, ..., N from left to right.

You have two pieces, initially placed on square A and B, respectively. You will be asked to process Q queries of the following kind, in the order received:

  • Given an integer x_i, move one of the two pieces of your choice to square x_i.

Here, it takes you one second to move a piece one square. That is, the time it takes to move a piece from square X to Y is |X-Y| seconds.

Your objective is to process all the queries in the shortest possible time.

You may only move the pieces in response to queries, and you may not move both pieces at the same time. Also, it is not allowed to rearrange the order in which queries are given. It is, however, allowed to have both pieces in the same square at the same time.

Constraints

  • 1 ≤ N, Q ≤ 200,000
  • 1 ≤ A, B ≤ N
  • 1 ≤ x_i ≤ N

Input

Input is given from Standard Input in the following format:

N Q A B
x_1 x_2 ... x_Q

Output

Let the shortest possible time to process all the queries be X seconds. Print X.


Sample Input 1

8 3 1 8
3 5 1

Sample Output 1

7

All the queries can be processed in seven seconds, by:

  • moving the piece at square 1 to 3
  • moving the piece at square 8 to 5
  • moving the piece at square 3 to 1

Sample Input 2

9 2 1 9
5 1

Sample Output 2

4

The piece at square 9 should be moved first.


Sample Input 3

9 2 1 9
5 9

Sample Output 3

4

The piece at square 1 should be moved first.


Sample Input 4

11 16 8 1
1 1 5 1 11 4 5 2 5 3 3 3 5 5 6 7

Sample Output 4

21

配点 : 900

問題文

N 個のマスが一列に並んでいます。マスには順に 1, 2, ..., N と番号を振ってあるものとします。

あなたはコマを 2 つ持っており、最初の時点ではマス A, B においてあります。

以下のクエリがQ 個与えられるので、順番に処理します。

  • x_i が与えられる。2 つのコマのどちらかをマス x_i に移動させる。どちらを移動させるかは好きに選んで良い。

ただし、コマは 1 マス分動くのに 1 秒の時間を必要とします。 つまり、マス X のコマをマス Y に動かすには |X-Y| 秒必要です。

あなたの目的は、出来る限り速く全てのクエリを処理することです。

なお、クエリ以外でのコマの移動は許されません。 また、クエリの順番を並び替えたり、コマを 2 個同時に動かしたりすることも許されません。 ただし、2 個のコマが同時に同じマスにいることは許されます。

制約

  • 1 ≦ N, Q ≦ 200,000
  • 1 ≦ A, B ≦ N
  • 1 ≦ x_i ≦ N

入力

入力は以下の形式で標準入力から与えられる。

N Q A B
x_1 x_2 ... x_Q

出力

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


入力例 1

8 3 1 8
3 5 1

出力例 1

7
  • マス 1 のコマをマス 3 に動かす
  • マス 8 のコマをマス 5 に動かす
  • マス 3 のコマをマス 1 に動かす

この通りにコマを動かすと 7 秒で全てのクエリを処理できます。


入力例 2

9 2 1 9
5 1

出力例 2

4

最初に動かすべきはマス 9 のコマです。


入力例 3

9 2 1 9
5 9

出力例 3

4

最初に動かすべきはマス 1 のコマです。


入力例 4

11 16 8 1
1 1 5 1 11 4 5 2 5 3 3 3 5 5 6 7

出力例 4

21

Submit提出する