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.

Constraints :

3 <= N <= 10^5
1 <= K <= N-2
1 <= arr[i] <= 10^9

Time Limit : 1 Sec

Sample Case :

5
1 2 3 7 8
2

Sample Output :
5

Explanation :
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

I was able to come to the conclusion that it will be solved using Binary Search over the value of diff and minimizing it by checking if it's possible to obtain that value by K removals but i couldn't deduce the function during the given time. Please help !!