[比赛/考试专用OJ] 该 OJ 与 oj.socoding.cn 数据不互通,首次使用请注册账号。

1061. 磁盘寻道(20分)

磁盘是一种机电设备,包括一个或多个物理盘片,每个盘片有一到两个盘面,每个盘面有若干条磁道,每条磁道有不同的编号。当读/写数据时,磁头会从原本所在的磁道移动到所要读/写的磁道,进行读/写操作。如图所示:

文件存储在磁道上,进程需要读/写文件。为了减少对文件的访问时间,应采用一种较优的磁盘调度算法,使得各进程对磁盘的平均访问时间最小。访问磁盘用时的大部分是寻道时间,所以磁盘调度的目标是使平均寻道时间最短。

一种常用的磁盘调度算法是最短寻道时间优先(shortest seek time first, SSTF)调度算法。设给定要访问的所有磁道号序列 a,和初始磁头所在的磁道号 b。定义两个磁道号 u,v 的距离是 |u-v|(也就是说只需把磁道看成是链,而不是环),那么该算法每次会选择与当前磁头所在磁道距离最近的磁道进行调度。

例如,设 b=100,a=(18,38,39,55,58,90,150,160,184),则调度序列如下表所示:

特别地,如果当前磁头左右两边都有距离相同的磁道待待访问,这里规定优先访问左边的磁道。

给定一个访问序列 a 和初始磁头位置 b,请你求出调度该序列 a 的移动距离序列。

输入

输入一行两个整数 n(1\le n\le 2\times 10^5),b(0\le b\le 10^9),其中 n 代表序列 a 的长度。

接下来输入一行 n 个整数,第 i 个整数代表 a_i(0\le a_i\le 10^9)

保证 \mathbf a 升序,即对 i > 1 恒满足 a_i \ge a_{i-1}

输出

输出一行 n 个整数,第 i 个整数代表 c_i,即进行第 i 次调度移动的距离(磁道数)。

样例

标准输入 复制文本
9 100
18 38 39 55 58 90 150 160 184
标准输出 复制文本
10 32 3 16 1 20 132 10 24
标准输入 复制文本
6 3
1 1 2 3 4 5
标准输出 复制文本
0 1 1 0 3 1
登录以提交代码。
单点时限 1 秒
内存限制 128 MB
提交 325
通过 56