[ARC073F] Many Moves

题意翻译

## 题意 在一行中有$n$个格子,从左往右编号为$1$到$n$。 有$2$颗棋子,一开始分别位于位置$A$和$B$。按顺序给出$Q$个要求,每个要求是如下形式: - 给出一个位置$x_i$,要求将两个棋子中任意一个移动到位置$x_i$。 将一颗棋子移动一格需要花费$1$秒,就是说将棋子从$X$位置移动到$Y$位置需要花费$|X-Y|$秒。 为了回答要求,你只能移动棋子,并且同一时刻只能移动一颗棋子。要求的顺序是不可更改的。在同一时间允许两颗棋子在同一个格子内。 ## 输入格式 第一行$4$个整数,分别为$n,Q,A,B$。 第二行$Q$个整数,第$i$个整数为$x_i$。 - $1\leq n,Q\leq 2\times 10^5$ - $1\leq A,B\leq n$ - $1\leq x_i\leq n$ ## 输出格式 最小需要多少秒回答全部要求。

题目描述

[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

8 3 1 8
3 5 1

输出样例 #1

7

输入样例 #2

9 2 1 9
5 1

输出样例 #2

4

输入样例 #3

9 2 1 9
5 9

输出样例 #3

4

输入样例 #4

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

输出样例 #4

21

说明

### 制約 - $ 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 $ のコマです。