원형 서가의 다음 높은 책

문제

한 도서관은 원형 전시대의 가장자리에 책 N권을 한 줄로 세워 놓았다. 전시대를 위에서 내려다보았을 때 책에는 시계 방향으로 1번부터 N번까지 번호가 붙어 있다. N번 책의 바로 다음에는 1번 책이 있으므로, 번호의 끝을 지나도 같은 방향으로 계속 이동할 수 있다. 각 책의 높이는 양의 정수로 기록되어 있다. 전시대 관리자는 각 책에 안내표를 붙이려고 한다. i번 책의 안내표에는 그 책에서 시계 방향으로 이동하며 만나는 책 중, 높이가 i번 책보다 엄격하게 큰 첫 번째 책까지의 이동 칸 수를 적는다. 바로 옆 책까지의 거리는 1칸이고, 책 하나를 지나 그다음 책까지의 거리는 2칸이다. 책의 높이가 같으면 더 높은 책으로 보지 않으므로 계속 다음 책을 살펴본다. 중간에 낮은 책이나 같은 높이의 책이 있어도 탐색은 막히지 않는다. 다만 안내표가 너무 먼 위치를 가리키지 않도록 모든 책에 공통으로 적용되는 탐색 한도 K가 있다. 각 책에서는 바로 다음 책부터 정확히 K칸 이내에 있는 책만 후보로 살펴본다. 이 범위에 더 높은 책이 없으면 안내표에는 0을 적는다. 범위 안에서 더 높은 책을 발견했다면 그중 가장 먼저 만나는 책만 선택하므로, 그보다 뒤에 더 높은 책이 있더라도 결과에 영향을 주지 않는다. 탐색 한도는 N보다 작으므로 한 번의 탐색에서 출발한 책을 다시 살펴보는 일은 없다. 그러나 번호가 작은 책이 번호가 큰 책의 탐색 대상이 될 수는 있다. 예를 들어 마지막 책에서 한 칸 이동하면 첫 번째 책을 살펴본다. 안내표를 계산하는 동안 책의 순서와 높이는 바뀌지 않으며, 한 책의 안내표 결과가 다른 책의 탐색 규칙을 바꾸지도 않는다. 모든 책의 안내표에 적힐 수를 번호 순서대로 구하는 프로그램을 작성한다.

입력

첫째 줄에 책의 수 N과 탐색 한도 K가 공백으로 구분되어 주어진다. 둘째 줄에 1번부터 N번까지의 책 높이 H₁, H₂, …, Hₙ이 공백으로 구분되어 주어진다.
2 ≤ N ≤ 60,000, 1 ≤ K ≤ N−1, 1 ≤ Hᵢ ≤ 999이다. 입력에 등장하는 모든 수는 정수이다.

출력

1번부터 N번까지 안내표에 적힐 수 N개를 한 줄에 공백으로 구분하여 출력한다. 각 수는 0 이상 K 이하의 정수이다.

4 3
5 1 3 4

0 1 1 1

4 2
2 2 1 3

0 2 1 0

5 4
7 7 7 7 7

0 0 0 0 0

출처: Devin.KR 자체 제작