University Admission#10672
Amin and Aziz successfully passed the technical stage of admission to the Korean university KAIST. Together with them, a total of candidates passed this stage. However, this does not yet guarantee their enrollment. In the next stage, the university will select students based on their social qualities. The social quality of the -th candidate is denoted as s_i.
The university conducts selection based on a parameter called the selection range, denoted as . The goal is to select the largest possible group of candidates such that the difference between the maximum and minimum social qualities in the group does not exceed . This ensures optimal interaction within the student community. Determine the maximum number of students the university can admit under this condition.
The first line contains two integers (1 \leq n \leq 10^{5}) and (0 \leq d \leq 10^{9}) — the number of candidates and the selection range.
The second line contains integers s_1, s_2, \dots, s_n (-10^{9} \leq s_i \leq 10^{9}) — the social qualities of the candidates.
Print the maximum number of students the university can admit.
Example 1
The university can admit a maximum of students, such as \{1, 3, 4\} or \{2, 3, 5\}. In both groups, the difference between the greatest and the least social qualities does not exceed d=3.
This problem consists of the following 4 subtasks:
