카페바자르의 애플리케이션

시간 제한1초메모리 제한2048 MB

요약

각 애플리케이션이 자신을 포함하고 최소 k개의 애플리케이션을 담은 연속 구간에서 얻을 수 있는 최소 순위를 구합니다.

난이도: 보통10점 중 7점
유형: 세그먼트 트리, 정렬, 배열
정답자: 아직 제출이 없습니다

문제

연말을 맞아 카페바자르는 $n$ 개 애플리케이션 각각의 사용자 수를 담은 목록을 공개했다. 각 애플리케이션은 광고 이미지에서 자신의 성과를 보여 주려 한다. 이미지에는 자신을 포함하는 목록의 연속된 부분 수열이 실린다. 신뢰도를 위해 이미지에는 자신을 포함해 최소 $k$ 개의 애플리케이션이 있어야 한다.

각 애플리케이션에 대해, 유효한 부분 수열 중에서 달성할 수 있는 최소 순위를 구하라. 부분 수열 안에서의 순위는 그 부분 수열에서 자신보다 사용자 수가 많은 애플리케이션의 개수에 1을 더한 값이다.

입력

첫 줄에 두 정수 $n$ 과 $k$ ( $1 \le k \le n \le 10^5$ )가 주어진다. $n$ 은 전체 애플리케이션의 개수이고, $k$ 는 광고 이미지에 들어가야 하는 애플리케이션의 최소 개수이다. 이어지는 $n$ 개의 줄에는 $i$ 번째 애플리케이션의 사용자 수 $c_i$ ( $1 \le c_i \le 10^8$ )가 한 줄에 하나씩 주어진다.

출력

한 줄에 공백으로 구분된 정수 $n$ 개를 출력한다. $i$ 번째 정수는 $i$ 번째 애플리케이션이 광고 이미지에서 달성할 수 있는 최소 순위이다.

예제2

예제 1

입력

예상 출력

2 3 1 2 3 1 1

예제 2
입력
```
3 2
10
10
10
```
예상 출력
```
1 1 1
```