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