← 返回题目列表

AtCoder · arc073_d

F. 很多动作

中文机器翻译题面 查看原题

分数: 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