D - Neighbor Distance Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

数直線があり、最初は座標 0 に人 0 がひとりで立っています。

これから、人 1,2,\dots,N がこの順に到着し、数直線上に立ちます。
人 i は座標 X_i に立ちます。なお、 X_i \ge 1 であり、全ての人について X_i は相異なります。

人が到着するたびに、以下の問いに答えてください。

  • 現在数直線に人 0,1,\dots,r の r+1 人が立っているとする。
  • このとき、 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
  • i \neq j ならば X_i \neq X_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 人到着します。
このうち最初の 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 です。

Score : 400 points

Problem Statement

There is a number line, and initially person 0 is standing alone at coordinate 0.

From now on, persons 1,2,\dots,N will arrive in this order and stand on the number line.
Person i stands at coordinate X_i. Here, X_i \ge 1, and X_i is distinct for all persons.

Each time a person arrives, answer the following question.

  • Suppose that currently r+1 persons 0,1,\dots,r are standing on the number line.
  • Here, define d_i as the distance to the nearest other person from person i.
    • More formally, \displaystyle d_i = \min_{0 \le j \le r, j \neq i} \vert X_i - X_j \vert.
  • Find the sum of this d, that is, \displaystyle \sum_{i=0}^r d_i.

Constraints

  • All input values are integers.
  • 1 \le N \le 5 \times 10^5
  • 1 \le X_i \le 10^9
  • X_i \neq X_j if i \neq j.

Input

The input is given from Standard Input in the following format:

N
X_1 X_2 \dots X_N

Output

Print N lines.
The i-th line ( 1 \le i \le N ) should contain the answer to the question when person i arrives.

Sample Input 1

10
5 2 7 4 108728325 390529120 597713292 322456626 845148281 812604915

Sample Output 1

10
7
8
8
108728326
390529121
523096670
452057486
699492475
517144218

In this input, 10 persons arrive.
The first four persons are explained below.

  • When person 1 arrives, there are persons at coordinates 0,5.
    • The required value is 5+5=10.
  • When person 2 arrives, there are persons at coordinates 0,2,5.
    • The required value is 2+2+3=7.
  • When person 3 arrives, there are persons at coordinates 0,2,5,7.
    • The required value is 2+2+2+2=8.
  • When person 4 arrives, there are persons at coordinates 0,2,4,5,7.
    • The required value is 2+2+1+1+2=8.