Максу нужно провести  k  соревнований. у макса уже есть  n  . для каждой известна её сложность. чтобы соревнование было наиболее интересным, в нём должны быть доступны как начинающим участникам, так и более опытным. интересность конкретного соревнования равна разности сложностей между самой трудной и самой простой данного соревнования (интересность соревнования из одной равна  0). макс хочет распределить между соревнованиями так, чтобы интересность самого скучного соревнования была максимальной и при этом не повторялись. пока макс думает над распределением , вам нужно узнать интересность самого скучного соревнования этого сезона (то есть соревнования с минимальной интересностью).

входные данные

первая строка содержит целые числа  n  и  k  (1≤k≤n≤2⋅1051≤k≤n≤2⋅105) — соответственно количество и количество соревнований.
вторая строка содержит  n  целых чисел  ai  (1≤ai≤1091≤ai≤109) — сложность .

выходные данные

выведите одно целое число — минимальную интересность среди всех  kk  проводимых соревнований.

примеры

входные данные

6 3 2 1 3 1 3 2

выходные данные

1

входные данные

7 2 8 8 8 8 1 2 3

выходные данные

6
подскажите, , алгоритм решения.
(без кода, просто словами)

p.s. желательно решение на питоне.
p.p.s. заранее !

​

89681355832    1   27.09.2019 14:11    1