Adjacent Cubes

Problem Statement

Adjacent Cubes You are given N cubes of wood arranged in strictly non-decreasing order . The length of the side of the i th cube is a[i] and side lengths of all the cubes are distinct. The first and the last cubes are glued at their positions and they cannot be moved. The difference, diff , of the cubes is defined as the maximum difference of the sides of two adjacent cubes for all the cubes in the arrangement: diff = max(a[i + 1] - a[i]) for 1 ≤ i You are required to minimize the diff value of the cube arrangement by removing exactly K cubes. Input Format The first line of the input consists of an integer N , representing the number of cubes. The second line consists of N space-separated integers a[i] , representing the lengths of the sides of the cubes. The third line contains a single integer K . Output Format Print a single integer that is the minimum diff value for the cube arrangement after removing K cubes. Constraints 3 ≤ N ≤ 10 5 1 ≤ K ≤ N - 2 1 ≤ a[i] ≤ 10 9 Examples Input: 4