12661266 SUSTech Online Judge
Problem 1266 --From-now-on minimum difference

1266: From-now-on minimum difference

Time Limit: 5 Sec  Memory Limit: 256 MB
Submit: 518  Solved: 122
[Submit][Status][Web Board]


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

Sample Input

1 2 3 4 5

Sample Output

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