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 x[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(x[i+1] - x[i]) for 1 ≤ i ≤ N-1 You are required to minimize the diff value of the cube arrangement by removing exactly K cubes. Input Format The first line contains a single integer N. The second line contains N space-separated integers x[i] where x[i] is the length of the side of the i th cube. 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 ≤ x[i] ≤ 10 9 Examples Example 1: Input: 4 1 4 8 1 1 Output: 3 In the given ar