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\) que representa la cantidad de jaulas libres de Samuel.
• Un entero \(m\) que representa la cantidad de hamsters que Samuel quiere comprar.
• Una serie de \(n\) enteros que representan las posiciones de las jaulas libres.

Salida

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

Ejemplos

ENTRADA

5
3
1 2 3 4 7

SALIDA

3

EXPLICACIÓN

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.

ENTRADA

6
2
1 2 3 4 5 1000000000

SALIDA

999999999

Límites

\( 2 \leq n,m \leq 10^5 \)

\( 1 \leq a[i] \leq 10^9 \) y todos sus elementos son distintos.