세탁소의 원형 운반대

문제

세탁소에는 세탁물 바구니를 일정한 간격으로 옮기는 원형 운반대가 있다. 운반대에는 N개의 자리가 있고, 이동 방향을 따라 1번부터 N번까지 번호가 붙어 있다. N번 자리 다음은 다시 1번 자리다. 각 자리에는 바구니가 정확히 하나씩 놓여 있으며, i번 바구니에 담긴 세탁물의 무게는 A_i다. 바구니는 운반대에서 내려놓거나 다른 자리로 옮기지 않는다. 무게가 같은 바구니도 번호가 다르면 서로 다른 바구니다. 운반대가 한 칸 움직일 때마다 다음 자리의 바구니가 검사 지점을 지난다. 세탁소는 각 바구니에 대해, 그 바구니가 검사 지점을 지난 직후부터 뒤따라오는 바구니를 순서대로 살펴보는 가상의 검사를 진행하려고 한다. i번 바구니를 기준으로 하면 i+1번, i+2번 순서로 검사하며, 번호가 N을 넘어가면 1번부터 계속한다. 각 기준 바구니에 대한 검사는 서로 독립적이므로 다른 검사에서 어떤 바구니를 확인했는지는 영향을 주지 않는다. 검사에서는 기준 바구니보다 무거운 바구니를 처음 만날 때까지 기다린다. 무게가 정확히 같은 바구니는 조건을 만족하지 않는다. 다만 기다릴 수 있는 이동 횟수에는 제한이 있어서, 기준 바구니 이후 최대 K칸까지만 살펴본다. 정확히 K칸 뒤의 바구니는 검사 대상에 포함한다. K는 N보다 작으므로 검사 중 기준 바구니 자신을 다시 만나는 일은 없다. K가 0이면 다른 바구니를 하나도 검사하지 않는다. 각 기준 바구니에 대해 제한 안에서 처음 만나는 더 무거운 바구니까지의 이동 횟수를 기록한다. 조건을 만족하는 바구니가 여러 개라면 이동 횟수가 가장 작은 하나를 사용한다. 제한 안에 더 무거운 바구니가 없다면 0을 기록한다. 번호가 작은 바구니를 우선하는 규칙은 없으며, 이동 방향으로 만나는 순서만 사용한다. 모든 바구니를 기준으로 검사를 진행했을 때 기록되는 N개의 값을 번호 순서대로 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N과 K가 주어진다. (1 ≤ N ≤ 60,000, 0 ≤ K ≤ N-1)
둘째 줄에 정수 A_1, A_2, ..., A_N이 공백으로 구분되어 주어진다. (1 ≤ A_i ≤ 99)

출력

i번 바구니의 검사 결과를 i번째 값으로 하여 N개의 정수를 한 줄에 공백으로 구분하여 출력한다. 제한 안에 더 무거운 바구니가 없다면 해당 값은 0이다.

5 3
4 2 5 3 5

2 1 0 1 0

3 1
1 3 2

1 0 0

1 0
8

0

출처: Devin.KR 자체 제작