D - Draw Your Cards Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

1 から N が書かれた N 枚のカードが裏向きで積まれた山札があり、上から i 枚目のカードには整数 P_i が書かれています。

この山札を使って、以下の行動を N ターン繰り返します。

  • 山札の一番上のカードを引いて、そこに書かれた整数を X とする。
  • 場に見えている表向きのカードであって書かれた整数が X 以上であるもののうち、書かれた整数が最小のものの上に、引いたカードを表向きで重ねる。もし場にそのようなカードがなければ、引いたカードをどれにも重ねずに表向きで場に置く。
  • その後、表向きのカードが K 枚重ねられた山が場にあればその山のカードを全て食べる。食べられたカードは全て場から消滅する。

各カードについて、何ターン目に食べられるか、あるいは最後まで食べられないかを求めてください。

制約

  • 入力は全て整数
  • 1 \le K \le N \le 2 \times 10^5
  • P は (1,2,\dots,N) の順列 ( (1,2,\dots,N) を並べ替えて得られる列 ) である

入力

入力は以下の形式で標準入力から与えられる。

N K
P_1 P_2 \dots P_N

出力

N 行出力せよ。
そのうち i (1 \le i \le N) 行目には、整数 i が書かれたカードについて、以下のように出力せよ。

  • もし i が書かれたカードが食べられるなら、それが何ターン目であるかを整数として出力せよ。
  • そうでないなら -1 と出力せよ。

入力例 1

5 2
3 5 2 1 4

出力例 1

4
3
3
-1
4

この入力では、 P=(3,5,2,1,4),K=2 です。

  • 1 ターン目に、 3 が書かれたカードが他のカードに重ねられずに表向きで場に置かれます。
  • 2 ターン目に、 5 が書かれたカードが他のカードに重ねられずに表向きで場に置かれます。
  • 3 ターン目に、 2 が書かれたカードが 3 が書かれたカードの上に表向きで重ねられます。
    • この時点で上から 2,3 が書かれたカードが表向きで重ねられた山が K=2 枚に達したので、両カードは食べられます。
  • 4 ターン目に、 1 が書かれたカードが 5 が書かれたカードの上に表向きで重ねられます。
    • この時点で上から 1,5 が書かれたカードが表向きで重ねられた山が K=2 枚に達したので、両カードは食べられます。
  • 5 ターン目に、 4 が書かれたカードが他のカードに重ねられずに表向きで場に置かれます。
  • 4 が書かれたカードは、最後まで食べられませんでした。

入力例 2

5 1
1 2 3 4 5

出力例 2

1
2
3
4
5

K=1 である場合、全てのカードは場に置かれたターンに食べられます。

入力例 3

15 3
3 14 15 9 2 6 5 13 1 7 10 11 8 12 4

出力例 3

9
9
9
15
15
6
-1
-1
6
-1
-1
-1
-1
6
15

Score : 400 points

Problem Statement

There is a deck consisting of N face-down cards with an integer from 1 through N written on them. The integer on the i-th card from the top is P_i.

Using this deck, you will perform N moves, each consisting of the following steps:

  • Draw the topmost card from the deck. Let X be the integer written on it.
  • Stack the drawn card, face up, onto the card with the smallest integer among the face-up topmost cards on the table with an integer greater than or equal to X written on them. If there is no such card on the table, put the drawn card on the table, face up, without stacking it onto any card.
  • Then, if there is a pile consisting of K face-up cards on the table, eat all those cards. The eaten cards all disappear from the table.

For each card, find which of the N moves eats it. If the card is not eaten until the end, report that fact.

Constraints

  • All values in input are integers.
  • 1 \le K \le N \le 2 \times 10^5
  • P is a permutation of (1,2,\dots,N) (i.e. a sequence obtained by rearranging (1,2,\dots,N)).

Input

Input is given from Standard Input in the following format:

N K
P_1 P_2 \dots P_N

Output

Print N lines.
The i-th line (1 \le i \le N) should describe the card with the integer i written on it. Specifically,

  • if the card with i written on it is eaten in the x-th move, print x;
  • if that card is not eaten in any move, print -1.

Sample Input 1

5 2
3 5 2 1 4

Sample Output 1

4
3
3
-1
4

In this input, P=(3,5,2,1,4) and K=2.

  • In the 1-st move, the card with 3 written on it is put on the table, face up, without stacked onto any card.
  • In the 2-nd move, the card with 5 written on it is put on the table, face up, without stacked onto any card.
  • In the 3-rd move, the card with 2 written on it is stacked, face up, onto the card with 3 written on it.
    • Now there is a pile consisting of K=2 face-up cards, on which 2 and 3 from the top are written, so these cards are eaten.
  • In the 4-th move, the card with 1 written on it is stacked, face up, onto the card with 5 written on it.
    • Now there is a pile consisting of K=2 face-up cards, on which 1 and 5 from the top are written, so these cards are eaten.
  • In the 5-th move, the card with 4 written on it is put on the table, face up, without stacked onto any card.
  • The card with 4 written on it was not eaten until the end.

Sample Input 2

5 1
1 2 3 4 5

Sample Output 2

1
2
3
4
5

If K=1, every card is eaten immediately after put on the table within a single move.

Sample Input 3

15 3
3 14 15 9 2 6 5 13 1 7 10 11 8 12 4

Sample Output 3

9
9
9
15
15
6
-1
-1
6
-1
-1
-1
-1
6
15