FastPrep

Description

Solutions

Submission

Ice Cream Sticks

🤘 INTERN

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.

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

Constraints:

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