問題
あなたは冒険ゲームを作成している．このゲームのプレイヤーは，主人公を操作して敵モンスターを倒し，主人公のレベルを上げることで冒険を進めていく．主人公の初期レベルは $1$ である．
このゲームには $N$ 種類の敵モンスターが用意されており，弱い順で $i$ 番目の種類の敵モンスターの強さは $s_i$ である．主人公が $1$ 回の戦闘を行うときには，次に戦う敵モンスターの種類を自由に選び，ちょうど $1$ 体の敵モンスターと戦闘を行う．主人公は同じ種類の敵モンスターと何回でも戦うことができ，何回でも倒すことができる．
あなたはいま，このゲームのバランスを調整するために，あるパラメーター $X$ を決めようとしている．パラメーター $X$ は正の整数であり下記のように使われる．
- 主人公のレベルが $L$ のとき，強さ $s_i$ が $L+X$ 未満の敵は倒せるが，それより強い敵モンスターは倒せない．
- 主人公のレベルが $L$ のとき，強さ $s_i$ の敵を倒すと $\max(1, X-|L-s_i|)$ だけ主人公のレベルが上がる．
このゲームは，最も強い（$N$ 種類目の）敵モンスターを初めて倒したときにゲームクリアとなる．あなたは，ゲームクリアまでに必要となる戦闘の回数が最低でも $M$ 回以上となるようにパラメーター $X$ を決めたいと考えている．ただし，敵モンスターの強さの設定によっては，$X$ をどのように設定しても $M$ 回未満の戦闘回数でゲームクリアできてしまうか，ゲームをクリアできなくなってしまう場合があることに注意せよ．
パラメーター $X$ を決めるとき，上記の条件を満たす範囲で最大のパラメーター値 $X_{max}$ を計算するプログラムを作ってほしい．
Input
入力は複数のデータセットから構成される．データセットの個数は最大でも $50$ を超えない．各データセットは次の形式で表される．
$N$ $M$ $s_1$ $s_2$ $\dots$ $s_N$
$1$ 行目は空白で区切られた $2$ つの整数 $N, M$ からなる．$N$ は用意した敵モンスターの種類の数，$M$ はゲームクリアまでに必要となるべき最小の戦闘の数であり，$1 \le N \le 100{,}000, 2 \le M \le 1{,}000{,}000$ を満たす．
$2$ 行目は空白で区切られた $N$ 個の整数 $s_1, s_2, \dots, s_N$ からなり，$N$ 種類の敵モンスターそれぞれの強さを表す．各 $s_i$ は $1 \le s_i \le 1{,}000{,}000$ を満たし，また $s_i \lt s_{i+1} (1 \le i \le N-1)$ である．
入力の終わりは空白で区切られた $2$ つのゼロからなる行で表される．
Output
各データセットについて，ゲームクリアまでに必要となる戦闘の回数が $M$ 回以上となるパラメーター $X$ の内の最大値 $X_{max}$ を整数で出力せよ．$X$ をどのように設定しても $M$ 回未満の戦闘回数でゲームクリアできてしまうかゲームをクリアできなくなってしまうテストケースの場合には $-1$ のみからなる行を出力せよ．
Sample Input
3 4 1 5 9 1 2 1 2 10 1 1000000 2 4 1 10 0 0
Output for Sample Input
3 -1 499996 4
$2$ 番目のテストケースでは，$X = 1$ と設定すると $1$ 回の戦闘でゲームをクリアできてしまう． このケースでは，必要となる戦闘の回数が $M$ 回以上であり，かつゲームをクリアできるように $X$ を設定することが出来ない． よって $-1$ のみからなる行を出力する．