Gia Huy là một bạn trẻ tham lam được giới giang hồ biết đến với bí danh huyvg, công việc của anh hàng ngày là đi thu tiền bảo kê của các sạp đồ ăn ven đường, biết số tiền anh thu được mỗi tháng là 1 dãy số nguyên ~𝑎1,𝑎2,…,𝑎𝑛~ với mỗi ~ai~ là tiền thu của giang hàng thứ i.

Vì được giải nhất QG, Gia Huy suýt đủ điều kiện để trở thành học sinh thủ đô nhưng thứ còn thiếu vẫn là 1 tấm lòng nhân hậu, do đó anh quyết định cải cách và từ tháng sau sẽ giảm việc thu tiền và chỉ thu ~n - k~ gian hàng thay vì n như ban đầu.

Không những thế, Gia Huy còn quyết định sau khi sort lại dãy tiền mới thì sẽ lấy ~W~ là hiệu lớn nhất giữa hai phần tử liên tiếp trong dãy để đem quyên góp vào trại cai nghiện Valorant của anh quantm, là một học sinh thông minh hãy thử xem Gia Huy nên dừng thu ~k~ gian hàng như thế nào để trại cai nghiện nhân được ít tài trợ nhất.

Input

• Dòng đầu chứa hai số nguyên dương ~𝑛,𝑘~ (~𝑘~ ≤ ~𝑛 − 2~);
• Dòng thứ hai chứa 𝑛 số nguyên ~𝑎1,𝑎2,…,𝑎𝑛~ (~|𝑎𝑖|~ ≤ 1e9);

Output

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

Subtask

• Subtask 1: ~𝑛 ≤ 100~;
• Subtask 2: ~𝑛 ≤ 2000~;
• Subtask 3: ~𝑛 ≤ 1e5~;

Sample Input

5 1
4 1 2 3 9

Sample Output

1