257. Largest Gap

Foundation1000 ms256 MBSolved by 0%

Sort n integers, then print the largest difference between two values that end up next to each other.

If n is 1 there are no adjacent pairs at all, so print 0.

This is the mirror of the previous problem and it is worth noticing that the minimum requires sorting while the maximum overall difference does not: the largest difference between ANY two values is simply the maximum minus the minimum. It is the largest ADJACENT gap that needs the ordering.

Constraints - `1 ≤ 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 largest gap between adjacent values after sorting, or 0 if there is only one value.

Input4 3 6 9 1

Output3

Notesorts to 1 3 6 9, whose largest adjacent gap is 3

Input1 1

Output0

Notehas no adjacent pair at all

Hint 1Approach

Hint 2Approach

Hint 3Pseudocode

Hint 4Full solution