256. Closest Two Values

Core1000 ms256 MBSolved by 0%

Print the smallest absolute difference between any two of n integers.

Checking every pair is n(n-1)/2 comparisons, which at 200000 is twenty billion and will not finish.

Sort first, and the closest two values must end up next to each other. That reduces the answer to a single sweep over adjacent pairs, because any pair further apart in the sorted order differs by at least as much.

Constraints - `2 ≤ n ≤ 200000` - `-1000000000 ≤ a[i] ≤ 1000000000`

Input

The first line contains an integer n. The second line contains n integers.

Output

Print one integer, the smallest absolute difference between two values.

Input4 3 8 15 17

Output2

Notehas its closest pair at the end of the sorted order

Input2 1 2

Output1

Noteis the smallest possible input

Hint 1Approach

Hint 2Approach

Hint 3Pseudocode

Hint 4Full solution