Choose Two Numbers With Minimum Difference

Interview

Time limit2sMemory limit128 MB

Summary

Given N integers and threshold M, find the minimum absolute difference between two elements that is still at least M.

Level: Medium4 of 10
Topics: Sorting, Two pointers, Binary search
Solved: No attempts yet

Problem

You are given a sequence A[1], A[2], ..., A[N] of N integers. Choose two numbers from the sequence, possibly the same element, so that their absolute difference is at least M.

Find the smallest possible difference among all valid choices.

Input

The first line contains two integers N and M.

Each of the next N lines contains one integer, in order: A[1], A[2], ..., A[N].

Output

Print the smallest difference that is at least M.

It is guaranteed that at least one valid choice exists.

Constraints

1 <= N <= 100,000
0 <= M <= 2,000,000,000
0 <= |A[i]| <= 1,000,000,000

Examples1

Example 1
Input
```
3 3
1
5
3
```
Expected output
```
4
```