AT_abc430_d [ABC430D] Neighbor Distance

数直線があり、最初は座標 $ 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 $ を求めよ。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ X_1 $ $ X_2 $ $ \dots $ $ X_N $

$ N $ 行に出力せよ。 そのうち $ i $ ( $ 1 \le i \le N $ ) 行目には、人 $ i $ が到着した時点での問いの答えを出力せよ。

### Sample Explanation 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 $ です。 ### Constraints - 入力は全て整数 - $ 1 \le N \le 5 \times 10^5 $ - $ 1 \le X_i \le 10^9 $ - $ i \neq j $ ならば $ X_i \neq X_j $