Problem F: From-now-on minimum difference

Problem F: From-now-on minimum difference

Time Limit: 5 Sec  Memory Limit: 256 MB
Submit: 533  Solved: 123
[Submit][Status][Web Board]

Description

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}|\).

Input

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\) ).

Output

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

Sample Input

5
1 2 3 4 5

Sample Output

1 1 1 1

HINT


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.

[Submit][Status]