Cafebazaar's Applications

Time limit1sMemory limit2048 MB

Summary

For each application, find the minimum rank it can reach in a contiguous subsequence that contains it and at least k applications.

Level: Medium7 of 10
Topics: Segment tree, Sorting, Array
Solved: No attempts yet

Problem

At the end of the year, Cafebazaar published a list of the number of users for each of its $n$ applications. Each application wants to show its success in an advertisement image. The image highlights a continuous subsequence of the list that contains the application itself. To be credible, the image must contain at least $k$ applications, including itself.

For each application, find the minimum rank it can achieve within any valid subsequence. The rank of an application within a subsequence is the number of applications in that subsequence with more users than it, plus one.

Input

The first line contains two integers $n$ and $k$ ( $1 \le k \le n \le 10^5$ ), where $n$ is the total number of applications and $k$ is the minimum number of applications in an advertisement image. Each of the next $n$ lines contains $c_i$ , the number of users of the $i$ th application ( $1 \le c_i \le 10^8$ ).

Output

Print $n$ space-separated integers on one line. The $i$ th integer is the minimum rank that the $i$ th application can achieve in an advertisement image.

Examples2

Example 1

Input

Expected output

2 3 1 2 3 1 1

Example 2
Input
```
3 2
10
10
10
```
Expected output
```
1 1 1
```