点我进入原题提交测试

题目描述

有一条数轴，最初0号人独自站在坐标0处。

从现在开始，编号为 $1,2,\dots,N$ 的人依次到达，并站在数轴上。第 $i$ 个人会站在坐标 $X_i$ 处，这里 $X_i \geq 1$，并且每个人的 $X_i$ 互不相同。

每次有新的人到达时，请回答以下问题：

• 假设当前有 $r+1$ 个人（编号为 $0,1,\dots,r$）站在数轴上。
• 对于每个人 $i$，定义 $d_i$ 为他到最近的其他人的距离。
  • 更正式地， $d_i = \min_{0 \leq j \leq r,\, j \neq i} |X_i - X_j|$。
• 求 $d$ 的总和，即 $\sum_{i=0}^r d_i$。

输入格式

输入从标准输入读取，格式如下：

$N \ X_1 \ X_2 \ \dots \ X_N$

输出格式

输出共 $N$ 行。
第 $i$ 行（$1 \leq i \leq N$）应在第 $i$ 个人到达时输出问题的答案。

10
5 2 7 4 108728325 390529120 597713292 322456626 845148281 812604915

10
7
8
8
108728326
390529121
523096670
452057486
699492475
517144218

说明/提示

样例解释 1

本样例中共有 $10$ 个人到来。
前 $4$ 个人的详细过程如下：

• 当第 $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$。

数据范围

• 所有输入的值均为整数。
• $1 \leq N \leq 5 \times 10^5$
• $1 \leq X_i \leq 10^9$
• 若 $i \neq j$，则 $X_i \neq X_j$。