F. Difference in Skill

Time limit: 1s Memory limit: 256MB Input: Output:

In a company there are nn employees. The skill level of the ii-th employee is denoted by an integer aia_i.

The company wants to start a new project, which requires some of the nn employees. A project is considered balanced if the difference in skill between any two employees assigned to the project is at most kk.

For every ii from 11 to nn, print the maximum number of employees that can be part of a balanced project which contains employee ii.

Input

The first line of input contains two integers nn and kk (1n21051 \le n \le 2 \cdot 10^5, 0k1090 \le k \le 10^9).

The second line of input contains nn integers a1,a2,,ana_1,a_2,\ldots,a_n (1ai1091 \le a_i \le 10^9) — the skill levels of the nn employees.

Output

For every ii from 11 to nn, print the maximum number of employees that can be part of a balanced project which contains employee ii.

Example 1

input

6 2
1 2 3 4 6 9

output

3 3 3 3 2 1 

Note

For the first employee, a balanced project can contain employees a1a_1, a2a_2 and a3a_3.
For the second employee, a balanced project can contain employees a1a_1, a2a_2 and a3a_3.
For the third employee, a balanced project can contain employees a1a_1, a2a_2 and a3a_3.
For the fourth employee, a balanced project can contain employees a2a_2, a3a_3 and a4a_4.
For the fifth employee, a balanced project can contain employees a4a_4 and a5a_5.
The sixth employee can be part of a balanced project only by themself.

Example 2

input

15 78
98 190 175 67 109 139 297 175 789 162 109 87 165 243 72

output

8 6 8 7 8 8 2 8 1 8 8 7 8 5 7  

Log in or sign up to be able to send submissions!