Descripción

A Samuel le encantan los hamsters y quiere comprar \(m\) crías para tenerlas de mascota. Sin embargo, el veterinario le advirtió que si los coloca demasiado cerca podrían pelearse, así que le recomendó maximizar la distancia mínima entre ellos.

Samuel tiene varias jaulas ordenadas y alineadas a lo largo de un pasillo, algunas de ellas ya están ocupadas por otras mascotas, por lo que solo dispone de \(n\) jaulas libres. Cada jaula libre tiene asignado un número entero que indica su posición en el pasillo, estas posiciones se te proporcionan en un arreglo \(a\), donde \(a_i\) representa la posición de la \(i-ésima\) jaula libre.

Samuel te pide ayuda para determinar cuál es la mayor distancia mínima posible entre dos hamsters si coloca exactamente \(m\) hamsters en las jaulas libres.

Entrada

Un entero \(n\) \((2 \leq n \leq 10^5)\) que representa la cantidad de jaulas libres de Samuel.

Un entero \(m\) \((2 \leq m \leq 10^5)\) que representa la cantidad de hamsters que Samuel quiere comprar.

Una serie de \(n\) enteros \(a_i\) \((1 \leq a_i \leq 10^9)\), donde todos son distintos, que representan las posiciones de las jaulas libres.

Salida

Un entero \(j\) que representa la máxima distancia mínima entre dos hamsters.

Ejemplo

Entrada

5
3
1 2 3 4 7

Salida

3

Entrada

6
2
1 2 3 4 5 1000000000

Salida

999999999

Nota

Samuel tiene \(5\) jaulas disponibles para colocar a los hamsters, sin embargo, en total tiene \(7\) jaulas, considerando la siguiente información basándose en el arreglo dado:

• La jaula \(1\) está libre.
• La jaula \(2\) está libre.
• La jaula \(3\) está libre.
• La jaula \(4\) está libre.
• La jaula \(5\) está ocupada porque no aparece en el arreglo.
• La jaula \(6\) está ocupada.
• La jaula \(7\) está libre.

Considerando esta información, se pueden colocar los \(3\) hamsters en las jaulas \(1, 4, 7\) dando una distancia mínima máxima entre ellos de \(3\). Se puede demostrar que no existe una distancia mayor que cumpla con las restricciones.