Per có ~n~ quyển sách, quyển thứ ~i~ nằm ở vị trí ~A_i~. Cô ấy muốn chọn ra ~k~ quyển để đọc.

Per cho rằng nếu chọn hai quyển sách quá gần nhau thì sẽ ảnh hưởng đến tính thẩm mỹ của giá sách. Vì vậy, cô ấy muốn tìm cách chọn ~k~ quyển sao cho khoảng cách nhỏ nhất giữa hai quyển được chọn liên tiếp là lớn nhất có thể.

Ví dụ, nếu Per chọn các quyển ở vị trí ~1~, ~3~, ~7~, ~10~ thì khoảng cách nhỏ nhất giữa hai quyển liên tiếp là ~2~, đó là khoảng cách giữa hai quyển ở vị trí ~1~ và ~3~.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~.
• Dòng thứ hai chứa ~n~ số nguyên ~A_1, A_2, \ldots, A_n~. Không có hai quyển sách nào ở cùng một vị trí.

Kết quả

In ra khoảng cách lớn nhất đảm bảo Per chọn được đúng ~k~ quyển sách.

Ví dụ

Đầu vào:

5 3
10 4 2 3 1

Đầu ra:

3

Giải thích: Chọn các quyển ở vị trí ~1~, ~4~, ~10~ thì khoảng cách giữa hai quyển liên tiếp lần lượt là ~3~ và ~6~, nhỏ nhất là ~3~. Không có cách chọn ~3~ quyển nào cho khoảng cách nhỏ nhất lớn hơn ~3~.

Giới hạn

• ~1 \le n \le 10^5~
• ~2 \le k \le n~
• ~1 \le A_i \le 10^9~

Các vị trí ~A_i~ đôi một khác nhau. Vì phải có ít nhất hai quyển sách được chọn thì "khoảng cách giữa hai quyển liên tiếp" mới có nghĩa, dữ liệu đảm bảo ~k \ge 2~.