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.

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

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.