Ice Cream Sticks

Given an array A[] denoting heights of N ice cream sticks and a positive integer K, modify the height of each stick either by increasing or decreasing them by K only once and then find out the least difference in the heights between the shortest and longest sticks. For example, consider that the heights are 0, 6, 11 and K=7. We can change 0 to 7, 6 to 9, and 11 to 4. The maximum difference is between 4 and 9, which is 5. We cannot minimise this difference. Input The first line of input contains a positive integer K. The second line of input contains a positive integer N, representing the number of sticks. The third line of the input contains N integers, representing the heights of N sticks. Output The minimum of the maximum difference of heights possible.

Constraints

0 < K ≤ 30 0 < N ≤ 30 0 ≤ A[i] ≤ 500

Example 1

Input:

K = 2
A = [2, 6, 9, 11]

Output:

5

Explanation: Explanation: 2->4, 6->8, 9->7, 11->9. So, the maximum difference is 5 (9-4).

Example 2

Input:

K = 20
A = [3, 4, 5]

Output:

2

Explanation: 3 → 23, 4 → 24, 5 → 25. So, the max different is 2 (25 − 23).