Cho dãy số nguyên \(a_{1},a_{2},\ldots,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ử 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.

Yêu cầu: Tìm cách xóa để \(w\) nhận giá trị nhỏ nhất.

Dữ liệu vào:

+ Dòng đầu chứa hai số nguyên dương \(n,k\ (k\ \leq \ n\ - \ 2)\);

+ Dòng thứ hai chứa 𝑛 số nguyên \(a_{1},a_{2},\ldots,a_{n}\ (|a_{i}| \leq 10^{9})\);

Kết quả: Gồm một dòng chứa một số là giá trị \(w\) nhỏ nhất tìm được.

Input	Output
5 1 4 1 2 3 9	1

Subtask 1: \(n\ \leq \ 100\);

Subtask 2: \(n\ \leq \ 2000\);

Subtask 3: \(n\ \leq \ 10^{5}\);