分数: 900 点
问题陈述
有 N 方块连续。方块已编号 1, 2, ..., N 从左到右。
你有两块,最初放置在正方形上 分别是 A 和 B。 系统会要求您处理 Q 以下类型的查询,按收到的顺序排列:
- 给定一个整数 x_i,将您选择的两块棋子之一移动到正方形 x_i.
在这里,您需要一秒钟才能将棋子移动一格。 即从正方形移动一个棋子所需的时间 X to Y is |X-Y| 秒。
您的目标是在尽可能短的时间内处理所有查询。
您只能移动棋子以响应查询,并且不能同时移动两个棋子。 此外,不允许重新排列给出查询的顺序。 然而,允许两颗棋子同时出现在同一个方格中。
约束
- 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 to 3
- 将棋子移动到正方形 8 to 5
- 将棋子移动到正方形 3 to 1
示例输入 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