Cho dãy số nguyên ~a_1, a_2, \ldots, a_n~ và số nguyên dương ~k~.

Yêu cầu: Thực hiện phép xóa ~k~ phần tử sao cho chênh lệch nhỏ nhất giữa 2 phần tử bất kỳ còn lại là lớn nhất.

Dữ liệu

• 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, \ldots, a_n~ (~|a_i| \le 10^9~).

Kết quả

• Gồm một dòng chứa một số là giá trị lớn nhất tìm được.

Ví dụ

Ví dụ 1

Input

5 1
4 1 2 3 9

Output

1

Giải thích: Xóa 1 phần tử bất kỳ, thì dãy còn lại luôn tồn tại 2 số tự nhiên liên tiếp nhau, nên độ chênh lệch lớn nhất là 1.

Ví dụ 2

Input

5 2
10 -5 3 -2 1

Output

7

Giải thích: Trong các cách xóa 2 phần tử bất kỳ, cách xóa chỉ còn 3 phần tử [10,-5,3] có độ chênh lệch nhỏ nhất là 7. Cách xóa này là cách xóa có độ chênh lệch nhỏ nhất giữa các phần tử là lớn nhất.

Giới hạn

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