AT_abc430_d [ABC430D] Neighbor Distance

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 $ .

The input is given from Standard Input in the following format: > $ N $ $ X_1 $ $ X_2 $ $ \dots $ $ X_N $

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

### Sample Explanation 1 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 $ . ### 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 $ .