[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 $ のコマです。