Problem D: Minimum Difference

## Problem D: Minimum Difference

Time Limit: 4 Sec  Memory Limit: 256 MB
Submit: 1453  Solved: 304
[Submit][Status][Web Board]

## Description

Given a sequence a with n items, the weights of each item are $$a_i$$. We define the minimum weight difference of $$a_i$$ as $$h_i = min_{j>i}|a_j−a_i|$$. Please compute the minimum weight difference of each item.

## Input

The first line has a integer n (2≤n≤2×10^6).

The second line has n space-separated integers: $$a_1,a_2,…,a_n$$   all the elements of the array a $$(1≤a_i≤10^9)$$.

## Output

Print space-separated integers:
$$h_1,h_2,…,h_{n−1}.$$

## Sample Input

5
1 2 3 4 5

## Sample Output

1 1 1 1

## HINT

It can be solved in a simple and efficient way by using sorting algorithm and linked list elegantly, . 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]