想当僵尸

题目描述

有 $N$ 个人，编号为 $1$ 到 $N$，站在一条数轴上。第 $i$ 个人站在坐标 $X_i$。这里 $X_i$ 都是偶数，并且 $X_1 < X_2 < \cdots < X_N$。

对每个 $k=1,2,\ldots,N$，求解以下问题：

在时刻 $0$，第 $k$ 个人变成僵尸，除他以外的所有人都还是人类。

从时刻 $0$ 开始，人类和僵尸都可以在数轴上以每秒不超过 $1$ 个单位的速度自由移动。当僵尸和人类处在同一坐标时，那个人类也会变成僵尸。

请求出所有人全部变成僵尸所需的最短时间。

在本题的约束下，可以证明答案一定是整数。

输入格式

输入第一行为一个整数 $N$。

第二行为 $N$ 个整数 $X_1,X_2,\ldots,X_N$，相邻两个数之间用一个空格隔开。

输出格式

输出 $N$ 行。第 $i$ 行表示当 $k=i$ 时，所有人全部变成僵尸所需的最短时间。

5
2 4 10 14 18

8
7
6
6
8

样例 1 解释

当 $k=1$ 时，如果第 $1$ 个人以速度 $1$ 向数轴正方向移动，第 $2,3,4,5$ 个人都以速度 $1$ 向负方向移动，那么到时刻 $8$ 时所有人都会变成僵尸。

当 $k=2$ 时，如果每个人按如下方式移动，那么到时刻 $7$ 时所有人都会变成僵尸：

• 第 $1$ 个人：以速度 $1$ 向正方向移动；
• 第 $2$ 个人：前 $3$ 个单位时间以速度 $1$ 向正方向移动，之后以速度 $1$ 向负方向移动；
• 第 $3$ 个人：前 $3$ 个单位时间以速度 $1$ 向负方向移动，之后以速度 $1$ 向正方向移动；
• 第 $4$ 个人：以速度 $1$ 向负方向移动；
• 第 $5$ 个人：以速度 $1$ 向负方向移动。

9
140322306 171833796 356303608 595703832 701965684 798563428 857902324 933683272 971602066

415639880
399884135
307649229
280821689
280821689
329120561
358790009
396680483
415639880

数据范围

对于所有测试数据，保证：

• $1 \le N \le 2 \times 10^5$；
• $0 \le X_1 < X_2 < \cdots < X_N \le 10^9$；
• $X_i$ 是偶数；
• 所有输入值均为整数。

子任务

本题共 20 个测试点，按测试点计分：

每个测试点单独评分，全部测试点的得分之和即为本题得分。