Trên một tuyến đường cao tốc có \(n\) vị trí có thể xây dựng trạm nghỉ, vị trí thứ \(i\) nằm tại tọa độ \(a_i\) trên trục đường thẳng. Do hạn chế về kinh phí, ban quản lý quyết định loại bỏ đúng \(k\) vị trí và chỉ giữ lại các vị trí còn lại để xây trạm nghỉ.

Yêu cầu đặt ra là sau khi loại bỏ \(k\) vị trí, khoảng cách nhỏ nhất giữa hai trạm nghỉ bất kỳ còn lại phải lớn nhất có thể.

Input

• Dòng đầu chứa hai số nguyên dương \(n, k\) (\(k \leq n - 2\)).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(|a_i| \leq 10^9\)).

Output

• In ra một số nguyên duy nhất là giá trị lớn nhất của khoảng cách nhỏ nhất giữa hai trạm nghỉ bất kỳ còn lại.

Example

5 1
4 1 2 3 9

1

5 2
10 -5 3 -2 1

7

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 20, k = 1\).
• Subtask \(2\) (\(30\%\) số điểm): \(20 < n \leq 100\).
• Subtask \(3\) (\(25\%\) số điểm): \(100 < n \leq 2000\).
• Subtask \(4\) (\(25\%\) số điểm): \(2000 < n \leq 10^5\).