B - Reverse Proxy Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

1,2,\dots,N の番号が付いた N 個の箱があります。最初は全ての箱が空です。

これから Q 個のボールが順番にやってきます。
高橋君は、数列 X=(X_1,X_2,\dots,X_Q) に従ってボールを箱に入れます。
具体的には、 i 番目にやってきたボールに次の処理を行います。

  • X_i \ge 1 である場合 : このボールを、箱 X_i に入れる。
  • X_i = 0 である場合 : このボールを、現在入っているボールが最も少ない箱のうち番号が最小である箱に入れる。

それぞれのボールをどの箱に入れたかを求めてください。

制約

  • 入力は全て整数
  • 1 \le N \le 100
  • 1 \le Q \le 100
  • 0 \le X_i \le N

入力

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

N Q
X_1 X_2 \dots X_Q

出力

i 番目にやってきたボールを箱 B_i に入れたとき、次の形式に従って出力せよ。

B_1 B_2 \dots B_Q

入力例 1

4 5
2 0 3 0 0

出力例 1

2 1 3 4 1

箱が 4 つあり、ボールは 5 個やってきます。

  • 最初、全ての箱は空です。
    • 各箱に入っているボールの数は箱 1 から順に 0,0,0,0 個です。
  • X_1=2 なので、 1 番目にやってきたボールを箱 2 に入れます。
    • 各箱に入っているボールの数は箱 1 から順に 0,1,0,0 個となります。
  • X_2=0 なので、 2 番目にやってきたボールを現在入っているボールが最も少ない箱のうち番号が最小である箱である箱 1 に入れます。
    • 各箱に入っているボールの数は箱 1 から順に 1,1,0,0 個となります。
  • X_3=3 なので、 3 番目にやってきたボールを箱 3 に入れます。
    • 各箱に入っているボールの数は箱 1 から順に 1,1,1,0 個となります。
  • X_4=0 なので、 4 番目にやってきたボールを現在入っているボールが最も少ない箱のうち番号が最小である箱である箱 4 に入れます。
    • 各箱に入っているボールの数は箱 1 から順に 1,1,1,1 個となります。
  • X_5=0 なので、 5 番目にやってきたボールを現在入っているボールが最も少ない箱のうち番号が最小である箱である箱 1 に入れます。
    • 各箱に入っているボールの数は箱 1 から順に 2,1,1,1 個となります。

各ボールを、やってきた順に箱 2,1,3,4,1 に入れました。よって、 2 1 3 4 1 と出力します。

入力例 2

3 7
1 1 0 0 0 0 0

出力例 2

1 1 2 3 2 3 1

入力例 3

6 20
4 6 0 3 4 2 6 5 2 3 0 3 2 5 0 3 5 0 2 0

出力例 3

4 6 1 3 4 2 6 5 2 3 1 3 2 5 1 3 5 4 2 6

Score : 200 points

Problem Statement

There are N boxes numbered 1,2,\dots,N. Initially, all boxes are empty.

Q balls will come in order.
Takahashi will put the balls into the boxes according to the sequence X=(X_1,X_2,\dots,X_Q).
Specifically, he performs the following process for the i-th ball:

  • If X_i \ge 1: Put this ball into box X_i.
  • If X_i = 0: Put this ball into the box with the smallest number among those containing the fewest balls.

Find which box each ball was put into.

Constraints

  • All input values are integers.
  • 1 \le N \le 100
  • 1 \le Q \le 100
  • 0 \le X_i \le N

Input

The input is given from Standard Input in the following format:

N Q
X_1 X_2 \dots X_Q

Output

If the i-th ball was put into box B_i, output in the following format:

B_1 B_2 \dots B_Q

Sample Input 1

4 5
2 0 3 0 0

Sample Output 1

2 1 3 4 1

There are 4 boxes, and 5 balls come.

  • Initially, all boxes are empty.
    • The numbers of balls in box 1,2,3,4 are 0,0,0,0, respectively.
  • Since X_1=2, put the 1st ball into box 2.
    • The numbers of balls in box 1,2,3,4 are 0,1,0,0, respectively.
  • Since X_2=0, put the 2nd ball into box 1, which has the smallest number among those containing the fewest balls.
    • The numbers of balls in box 1,2,3,4 are 1,1,0,0, respectively.
  • Since X_3=3, put the 3rd ball into box 3.
    • The numbers of balls in box 1,2,3,4 are 1,1,1,0, respectively.
  • Since X_4=0, put the 4th ball into box 4, which has the smallest number among those containing the fewest balls.
    • The numbers of balls in box 1,2,3,4 are 1,1,1,1, respectively.
  • Since X_5=0, put the 5th ball into box 1, which has the smallest number among those containing the fewest balls.
    • The numbers of balls in box 1,2,3,4 are 2,1,1,1, respectively.

The balls were put into boxes 2,1,3,4,1 in order. Thus, output 2 1 3 4 1.

Sample Input 2

3 7
1 1 0 0 0 0 0

Sample Output 2

1 1 2 3 2 3 1

Sample Input 3

6 20
4 6 0 3 4 2 6 5 2 3 0 3 2 5 0 3 5 0 2 0

Sample Output 3

4 6 1 3 4 2 6 5 2 3 1 3 2 5 1 3 5 4 2 6