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