← 返回题目列表

AtCoder · abc430_d

G. 邻居距离

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

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