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.