分数: 400 点
问题陈述
有一条数轴,最初是人 0 独自站在坐标处 0.
从现在起,人们 1,2,\dots,N 将按此顺序到达并站在数轴上。
人 i 站在坐标处 X_i。在这里, X_i \ge 1,和 X_i 对于所有人来说都是不同的。
每次有人到达时,请回答以下问题。
- 假设当前 r+1 人 0,1,\dots,r 站在数轴上。
- 在这里,定义 d_i 作为人到最近的其他人的距离 i.
- 更正式地说, \displaystyle d_i = \min_{0 \le j \le r, j \neq i} \vert X_i - X_j \vert.
- 求这个的总和 d,即 \displaystyle \sum_{i=0}^r d_i.
约束
- 所有输入值均为整数。
- 1 \le N \le 5 \times 10^5
- 1 \le X_i \le 10^9
- X_i \neq X_j if i \neq j.
输入
输入由标准输入按以下格式给出:
N X_1 X_2 \dots X_N
输出
打印 N 行。
的 i- 第行 ( 1 \le i \le N )应包含以下问题的答案: i 到达。
示例输入 1
10 5 2 7 4 108728325 390529120 597713292 322456626 845148281 812604915
示例输出 1
10 7 8 8 108728326 390529121 523096670 452057486 699492475 517144218
在此输入中, 10 人员到达。
前四人解释如下。
- 当人 1 到达,坐标有人 0,5.
- 所需的值为 5+5=10.
- 当人 2 到达,坐标有人 0,2,5.
- 所需的值为 2+2+3=7.
- 当人 3 到达,坐标有人 0,2,5,7.
- 所需的值为 2+2+2+2=8.
- 当人 4 到达,坐标有人 0,2,4,5,7.
- 所需的值为 2+2+1+1+2=8.