Cho dãy số nguyên \(a_1, a_2, \dots, a_n\) và số nguyên dương \(k\). Thực hiện phép xóa \(k\) phần tử, sau đó sắp xếp các phần tử còn lại theo thứ tự tăng dần. Gọi \(W\) là hiệu lớn nhất giữa hai phần tử liên tiếp trong dãy sau khi đã sắp xếp.

Yêu cầu

Tìm cách xóa \(k\) phần tử sao cho \(W\) nhận giá trị nhỏ nhất.

Input

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

Output

• Gồm một dòng duy nhất chứa giá trị \(W\) nhỏ nhất tìm được.

Example

5 1
4 1 2 3 9

1

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \le 100\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \le 2000\).
• Subtask \(3\) (\(40\%\) số điểm): \(n \le 10^5\).

Nguồn: Thầy Đông '1920