XXVI Olimpíada Brasileira de Informática
Submeta sua solução

Nome do arquivo: vende.x, onde x deve ser c, cpp, java, js ou py

Vende-se

A Otacílio Busílis Imóveis (OBI) é a maior imobiliária de Nlogópolis, especializada no aluguel de prédios comerciais; todas as suas propriedades se localizam na Avenida Doutor Otacílio Busílis, assim chamada em homenagem ao fundador da OBI.

Devido à crise econômica mundial, a OBI precisa vender K de seus imóveis para levantar capital de giro. Dr.Otacílio quer que os prédios restantes após a venda sejam o mais próximos possível --- ou seja, a distância entre o primeiro e o último prédios restantes deve ser a menor possível.

Infelizmente, a OBI é proprietária de tantos prédios que o Dr.Otacílio não sabe quais prédios ele deve vender; ele lhe contratou para que você escreva um programa que determina qual é a mínima distância possível entre o primeiro e o último prédios da OBI na avenida, após a venda de K prédios.

Entrada

A primeira linha da entrada contém os inteiros N e K, indicando, respectivamente, quantos prédios a OBI possui, e quantos prédios ela pretende vender. A linha seguinte contém N inteiros X_i, indicando a distância de cada um dos N prédios ao início da avenida, em metros.

Saída

A saída deve conter um único inteiro indicando a menor distância possível entre o primeiro e o último prédio possuídos pela OBI após a venda.

Restrições

  • 3 ≤ N ≤ 105
  • N - K ≥ 2
  • 1 ≤ X_i ≤ 106
  • todos os X_i são distintos

Informações sobre a pontuação

  • Em um conjunto de casos de teste que totaliza 30 pontos, N ≤ 10
  • Em um conjunto de casos de teste que totaliza 70 pontos, N ≤ 2000

Exemplos

Entrada
5 2
10 7 4 8 2
Saída
3
	
Entrada
8 6
16 11 1 7 29 4 22 2
Saída
1
	
Tarefas Programação Nível 2
Promoção
logo sbc
Patrocínio
Apoio
Coordenação