Yuki is a clever girl and she is good at mathematics. One day, she gets an array \(a\) of \(n\) integers: \(a_{1}, a_{2}, \ldots, a_{n}\). She wants to know the from-now-on minimum difference of \(a_{1}, a_{2}, \ldots, a_{n - 1}\), and your task is to help her to calculate them. The from-now-on minimum difference of \(a_{i}\), denoted by \(h_{i}\), is defined as: \(h_{i} = \min_{j > i} |a_{j} - a_{i}|\).

The first line contains one integer: \(n\) (\(2 \leq n \leq 2 \times 10^{6}\)). The second line contains \(n\) space-separated integers: \(a_{1}, a_{2}, \ldots, a_{n}\) — elements of the array \(a\) (\(1 \leq a_{i} \leq 10^9\) ).

Print one line with \(n - 1\) space-separated intergers: \(h_{1}, h_{2}, \ldots, h_{n - 1}\).

You may solve this problem using some advanced data structures. However, it can be solved in a simple and efficient way merely by sorting algorithm and linked list.

Please note that the size of input might be really large, so you might want to use an efficient way to read the input data.