penguin's compare heights

2 secs 1024 MB
penguin8331

問題文


匹のペンギンがいます。
各ペンギンの身長はそれぞれ です。
いま飼育員のTysonくんはこのすべてのペンギンを 個の水槽に分けようとしています。
ひとつの水槽に入れるペンギンの数に上限はなく、また0匹でもよいものとします。
しかしTyson君は身長でしかペンギンを見分けることができないため同じ水槽に同じ身長のペンギンがいてはいけません。
また全てのペンギンはそのペンギンが入っている水槽で最も身長の高いペンギンとの身長の差だけ不幸さを感じます。
各ペンギンの不幸さの最大値をもっとも小さくするとき、その値を答えてください。

制約


  • 入力される値は全て整数

入力



出力


計算結果を一行に出力せよ。
しかし水槽にすべてのペンギンが入らない場合は -1 を出力せよ。

サンプル


入力例1
5 2
6 6 3 5 10 
出力例1
4

身長が 6,3,5 のペンギンと 6,10 のペンギンで 2 つの水槽に分けるのが最適です。
身長が 6 のペンギンを 2 匹とも同じ水槽に入れてはならないことに注意してください。


入力例2
3 1
100 100 100
出力例2
-1

3匹のペンギンは同じ身長であるため 1 つの水槽にいれることができません。

提出


Go (1.14)