There are N positive numbers in an array present is strictly non-decreasing order.
The difference diff is defined as the maximum difference between the two adjacent elements of the array as
diff = max( arr[i+1] - arr[i] ) for 1<= i <= N-1.
You need to minimize the diff by removing exactly K elements.
Note : The first and last elements of the array are fixed (You cannot remove them).
Input Format :
The first line contains a single integer N.
The second line contains N space-separated integers.
The third line contains a single integer K.
Output Format :
Print a the minimized diff value.
3 <= N <= 10^5
1 <= K <= N-2
1 <= arr[i] <= 10^9
Time Limit : 1 Sec
Sample Case :
1 2 3 7 8
Sample Output :
There are 3 ways to remove K elements as (1,7,8) (1,3,8) and (1,2,8).
Diff values for the above cases will be 6 (7-1), 5 (8-3) and 6 (8-2).
Therefore the minimum value is 5