Cho một dãy gồm \(N\) số tự nhiên \(a_1, a_2, a_3...a_n\) \((3 \le N \le 10^6; |a_i| \le 10^6, 1 \le i \le N)\)

Xóa \(K\) số bất kỳ từ dãy số \(a_1, a_2, a_3...a_n\) \((1 \le K \le N-2)\). Sau khi xóa, gọi \(max\) là chênh lệch lớn nhất giữa hai số bất kỳ trong dãy số.

Yêu cầu: Tìm cách xóa \(K\) phần tử sao cho \(max\) là nhỏ nhất

Dữ liệu vào:

• Dòng 1: Hai số tự nhiên \(N\) và \(K\)
• Dòng 2: \(N\) số tự nhiên \(a_1, a_2, a_3...a_n\)

Dữ liệu ra:

• Một số nguyên duy nhất là kết quả \(max\) tìm được.

Ràng buộc:

• Có 40% số test tương ứng 40% số điểm \(K \le 2\)
• Có 40% số test tương ứng 40% số điểm \(2 \le K \le 4\)
• Có 20% số test còn lại không có ràng buộc gì thêm

Input 1

5 1
1 2 6 8 10

Output 1

7

Input 2

5 2
1 2 6 8 10

Output 2

4