Nhà thám hiểm dũng cảm

Bạn là một nhà thám hiểm dũng cảm, hành trình qua một dãy các vùng đất bí ẩn. Mỗi vùng đất này được biểu diễn bằng một dãy số nguyên dương \(h_1, h_2, \dots, h_N\), với \(h_i\) là độ cao của vùng đất thứ \(i\). Từ một vùng đất ban đầu, bạn có thể di chuyển sang các vùng đất lân cận theo một số điều kiện đặc biệt.

Cụ thể, với mỗi vùng đất \(i\), hãy tìm số lượng các vùng đất khác mà bạn có thể di chuyển đến lớn nhất dựa trên một độ cao giới hạn \(K\) cho trước. Mục tiêu của bạn là chinh phục càng nhiều vùng đất càng tốt, nhưng để di chuyển, bạn phải tuân theo những quy tắc nghiêm ngặt sau:

• Từ vị trí \(i\), bạn có thể di chuyển tới các vùng đất liền kề như \(i+1\), \(i+2\), \(\dots\) hoặc \(i-1\), \(i-2\), \(\dots\).

• Bạn có thể di chuyển từ vùng đất \(i\) đến vùng đất \(j\) nếu và chỉ nếu một trong các điều kiện sau được thỏa mãn:

• \(h[i] \geq h[j]\) (có nghĩa là vùng đất đích không cao hơn vùng đất hiện tại).

• \(h[i] < h[j]\) và \(h[j] - h[i] \leq K\) (chênh lệch độ cao giữa vùng đất đích và vùng đất hiện tại không vượt quá \(K\)).

Với mỗi vùng đất \(i\), hãy tìm số lượng vùng đất tối đa mà bạn có thể chinh phục từ vùng đất đó, tuân theo các quy tắc trên.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(N\) và \(K\) (\(1 \leq N \leq 10^5\), \(1 \leq K \leq 10^9\)) --- số lượng vùng đất và độ cao giới hạn.

• Dòng thứ hai chứa \(N\) số nguyên dương \(h_1, h_2, \dots, h_N\) (\(1 \leq h_i \leq 10^9\)), biểu diễn độ cao của từng vùng đất.

Output

In ra \(N\) số nguyên không âm, số thứ \(i\) chứa số lượng vùng đất tối đa mà bạn có thể chinh phục được khi bắt đầu từ vùng đất \(i\). Mỗi số cách nhau một dấu cách.

Example

7 3
3 7 4 2 5 6 10

1 7 6 3 6 6 7 

Scoring

• \(40\%\) số test có \(N \leq 2000\).
• \(60\%\) số test còn lại không có ràng buộc gì thêm.