Bác Bình là kỹ sư viễn thông cho huyện miền núi. Huyện có \(N\) cụm dân cư nằm rải rác trên trục đường chính, cụm thứ \(i\) tọa độ nguyên \(x_i\) (\(x_1 < x_2 < \ldots < x_N\)). Để phủ sóng viễn thông cho toàn bộ huyện, Bác Bình cần lắp đúng \(K\) trạm phát sóng. Mỗi trạm đặt tại vị trí nguyên \(p\) sẽ có bán kính phủ \(R\), phủ sóng cho mọi cụm dân cư có \(|x - p| \le R\).

Hãy giúp bác Bình tìm bán kính \(R\) nhỏ nhất sao cho có cách lắp \(K\) trạm phủ được tất cả \(N\) cụm dân cư.

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên \(N\) và \(K\) (\(1 \le K \le 50\), \(K \le N \le 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên \(x_1, x_2, \ldots, x_N\) (\(1 \le x_i \le 10^9\), phân biệt tăng dần).

Định dạng đầu ra

• In ra một số nguyên là bán kính phủ nhỏ nhất \(R\).

Ví dụ

Input:

5 2
1 7 12 19 25

Output:

11

Giải thích: Bán kính \(R = 11\):

• Đặt trạm \(1\) tại \(8\): phủ \([-3, 19]\) chứa \(1, 7, 12, 19\).
• Đặt trạm \(2\) tại \(25\): phủ \([14, 36]\) chứa \(19, 25\).

Ràng buộc

• \(1 \le K \le 50\), \(K \le N \le 10^5\).
• \(1 \le x_i \le 10^9\).