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 is5 (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).
0 < K <= 300 < N <= 300 <= A[i] <= 500
input:
output: