Có ~N~ thỏi vàng được cố định tại các vị trí ~X_1, X_2, X_3, \ldots, X_N~ trên một trục nằm ngang.

Nếu người chơi đào tại vị trí ~X~ với lực đập ~R~, người chơi có thể lấy được các thỏi vàng cách vị trí ~X~ tối đa ~R~ đơn vị chiều dài, tức là các thỏi vàng có vị trí nằm trong đoạn ~[X - R, X + R]~.

Người chơi được đào tối đa ~K~ lần và lực đập ~R~ là như nhau ở tất cả các lần đào. Nếu chọn lực đập ~R~ càng nhỏ thì số điểm đạt được càng cao.

Hãy tìm giá trị nguyên ~R~ nhỏ nhất để người chơi có thể lấy được toàn bộ ~N~ thỏi vàng sau tối đa ~K~ lần đào.

Dữ liệu vào

Dòng đầu chứa hai số nguyên ~N~ và ~K~, lần lượt là số lượng thỏi vàng và số lần đào tối đa.

~N~ dòng tiếp theo, dòng thứ ~i~ chứa một số nguyên ~X_i~, là vị trí của thỏi vàng thứ ~i~.

Dữ liệu ra

In ra một số nguyên duy nhất là giá trị lực đập ~R~ nhỏ nhất để có thể lấy được toàn bộ ~N~ thỏi vàng sau tối đa ~K~ lần đào.

Giới hạn

~1 \le N \le 50000~

~1 \le K \le 20~

~0 \le X_i \le 10^9~

Scoring

20% số điểm có ~K = 1~ và ~N \le 1000~.

20% số điểm có ~K = 2~ và ~N \le 10000~.

60% số điểm có ~K \le 20~ và ~N \le 50000~.

V? d?

Input

1 1
0

Output

0