Trong trò chơi tìm kho báu, trên con đường có \(N\) cây, cây thứ \(i\) có độ cao \(H_i\).
Để tìm được kho báu, Hoàng được đưa cho một khóa \(K\). Hoàng muốn đánh dấu nhiều cây nhất sao cho độ chênh lệch giữa cây cao nhất và cây thấp nhất trong các cây được đánh dấu không vượt quá \(K\), tức là nếu tập các cây được đánh dấu có các độ cao \(x_1,x_2,\ldots,x_m\) thì
Yêu cầu: Hãy xác định số lượng cây được đánh dấu nhiều nhất và in ra chiều cao của một cách chọn đạt giá trị lớn nhất đó. Nếu không thể đánh dấu cây nào, in ra \(-1\).
Input
Dòng đầu chứa hai số nguyên \(N\) và \(K\) \((1 \le N \le 2\cdot 10^4,\ 1 \le K \le 10^9)\).
Dòng thứ hai chứa \(N\) số nguyên \(H_1,H_2,\ldots,H_N\) \((1 \le H_i \le 10^9)\).
Output
Nếu không thể đánh dấu cây nào, in ra \(-1\).
Ngược lại:
- Dòng đầu in ra số lượng cây lớn nhất có thể đánh dấu.
- Dòng thứ hai in ra chiều cao của các cây trong một cách chọn tối ưu, các số cách nhau bởi một dấu cách.
Sample Input 1
8 10
10 5 90 6 20 9 16 100
Sample Output 1
4
5 6 9 10
Bình luận
Đăng nhập để bình luận
Chưa có bình luận nào.