Cafebazaar’s Applications

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

요약

각 원소가 자기 자신을 포함하고 길이가 k 이상인 연속 부분 배열 안에서 가질 수 있는 최소 순위를 구한다.

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

문제

It’s the end of the year, and Cafebazaar has released a list, containing the number of users of each of its $n$ applications. Now, each application is eager to showcase its success through an advertisement image, which highlights a continuous subset of the application list containing the application itself. Also, for the image to be credible, it should contain at least $k$ applications, including itself.

For each application in this list, we need to determine the minimum possible rank this application can achieve within any valid subset, according to the number of users. The rank of an application within a subset is defined by the number of applications in that subset that have more users than it, plus one.

입력

The first line of input consists of two integers $n$ and $k$ ( $1 \le k \le n \le 10^5$ ), where $n$ represents the total number of applications and $k$ represents the minimum number of applications in an advertisement image. The following $n$ lines contain information about each application: the $i$ th line contain $c\_i$ , representing the number of users for the $i$ th application ( $1 \le c\_i \le 10^8$ ).

출력

In the only line of output print $n$ space-separated integers. The $i$ th integer should be the minimum rank that $i$ th application can achieve within an advertisement image.

예제2

예제 1

입력

예상 출력

2 3 1 2 3 1 1

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