Câu lạc bộ Lập trình của Trường Công nghệ Thông tin và Truyền thông có ~n~ thành viên, thành viên thứ ~i~ có điểm xếp hạng ~a_i~. Trước mỗi buổi đấu tập, ban chủ nhiệm muốn ghép cặp các thành viên có trình độ gần nhau, vì vậy cần khảo sát độ chênh giữa các cặp.

Xét tất cả ~\dfrac{n(n-1)}{2}~ cặp thành viên ~(i, j)~ với ~1 \le i < j \le n~; độ chênh của cặp ~(i, j)~ là ~|a_i - a_j|~. Viết độ chênh của tất cả các cặp thành một dãy rồi sắp xếp dãy đó theo thứ tự không giảm. Các giá trị bằng nhau vẫn được giữ lại đầy đủ, nên dãy có đúng ~\dfrac{n(n-1)}{2}~ phần tử.

Yêu cầu

Hãy cho biết phần tử đứng thứ ~k~ (đánh số từ ~1~) của dãy độ chênh đã sắp xếp.

Dữ liệu vào

• Dòng thứ nhất chứa hai số nguyên ~n~ và ~k~;
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~, các số cách nhau bởi dấu cách.

Kết quả ra

Ghi ra một số nguyên duy nhất là độ chênh đứng thứ ~k~.

Ràng buộc

~2 \le n \le 2 \cdot 10^5~; ~0 \le a_i \le 10^9~; ~1 \le k \le \dfrac{n(n-1)}{2}~.

• Subtask 1 (15% số điểm – test 01–04): ~n \le 1000~;
• Subtask 2 (20% số điểm – test 05–08): ~k = 1~;
• Subtask 3 (25% số điểm – test 09–13): ~a_i \le 2000~;
• Subtask 4 (40% số điểm – test 14–20): không có ràng buộc bổ sung.

Lưu ý: số cặp, và do đó cả ~k~, có thể lên tới khoảng ~2 \cdot 10^{10}~, vượt quá phạm vi kiểu số nguyên 32 bit.

Ví dụ

Dữ liệu vào mẫu 1

5 7
7 1 4 10 4

Kết quả ra mẫu 1

6

Giải thích

Có ~10~ cặp. Độ chênh của các cặp ~(1,2), (1,3), (1,4), (1,5), (2,3), (2,4), (2,5), (3,4), (3,5), (4,5)~ lần lượt là ~6, 3, 3, 3, 3, 9, 3, 6, 0, 6~. Sắp xếp không giảm ta được dãy ~0, 3, 3, 3, 3, 3, 6, 6, 6, 9~; phần tử đứng thứ ~7~ là ~6~.