J - Sushi-go-round Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 6 点

注意

この問題に対する言及は、2020/6/6 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

寿司を食べたことのない N 人の子供たちが回転寿司屋にやってきました。 それぞれの子供には 1,2,3,\ldots,N の番号がついています。

M 個の寿司が順番に流れてきます。i 番目に流れてくる寿司の美味しさは a_i です。 寿司は 1,2,3,\ldots,N 番の子供の前をこの順に通ります。

それぞれの子供は自分の前に寿司が流れてきたとき、以下のいずれかの条件を満たすときに限りその寿司を取って食べます。それ以外の場合は何もしません。

  • まだ寿司を一つも食べていない
  • 今までに食べたどの寿司よりも美味しさが大きい

それぞれの寿司について、何番の子供が食べるかを求めてください。

制約

  • 与えられる入力は全て整数
  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 3 \times 10^5
  • 1 \leq a_i \leq 10^9

入力

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

N M
a_1 a_2 \cdots a_M

出力

M 行出力せよ。i 行目では i 番目に流れてきた寿司を食べた子供の番号を出力せよ。誰にも食べられない場合は -1 を出力せよ。

入力例 1

2 5
5 3 2 4 8

出力例 1

1
2
-1
2
1
  • 1 番目に美味しさ 5 の寿司が流れてきます。
    • 子供 1 の前を通ったとき、子供 1 はまだ寿司を食べていないので子供 1 はこの寿司を取って食べます。
  • 2 番目に美味しさ 3 の寿司が流れてきます。
    • 子供 1 の前を通ったとき、子供 1 が今までに食べた寿司にこの寿司の美味しさ以上のものがあるので子供 1 はこの寿司を取りません。
    • 子供 2 の前を通ったとき、子供 2 はまだ寿司を食べていないので子供 2 はこの寿司を取って食べます。
  • 3 番目に美味しさ 2 の寿司が流れてきます。
    • 子供 1 の前を通ったとき、子供 1 が今までに食べた寿司にこの寿司の美味しさ以上のものがあるので子供 1 はこの寿司を取りません。
    • 子供 2 の前を通ったとき、子供 2 が今までに食べた寿司にこの寿司の美味しさ以上のものがあるので子供 2 はこの寿司を取りません。
  • 4 番目に美味しさ 4 の寿司が流れてきます。
    • 子供 1 の前を通ったとき、子供 1 が今までに食べた寿司にこの寿司の美味しさ以上のものがあるので子供 1 はこの寿司を取りません。
    • 子供 2 の前を通ったとき、この寿司は子供 2 が今までに食べたどの寿司よりも美味しさが大きいので子供 2 はこの寿司を取って食べます。
  • 5 番目に美味しさ 8 の寿司が流れてきます。
    • 子供 1 の前を通ったとき、この寿司は子供 1 が今までに食べたどの寿司よりも美味しさが大きいので子供 1 はこの寿司を取って食べます。

入力例 2

5 10
13 16 6 15 10 18 13 17 11 3

出力例 2

1
1
2
2
3
1
3
2
4
5

入力例 3

10 30
35 23 43 33 38 25 22 39 22 6 41 1 15 41 3 20 50 17 25 14 1 22 5 10 34 38 1 12 15 1

出力例 3

1
2
1
2
2
3
4
2
5
6
2
7
6
3
7
6
1
7
4
8
9
6
9
9
4
4
10
9
8
-1

Score : 6 points

Warning

Do not make any mention of this problem until June 6, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

N children, who have never had sushi, have come to a sushi-go-round. The children are numbered 1,2,3,\ldots,N.

The conveyer belt will convey M sushi plates one by one. The deliciousness of the i-th plate is a_i. The plates will pass in front of Child 1, 2, 3, \ldots, N, in this order.

When a plate is passing in front of a child, he/she will pick up the plate and eat it if and only if one of the following conditions is satisfied:

  • He/she has never had a plate.
  • The deliciousness of the plate is greater than those of all plates he/she has had so far.

For each plate, find which child will have it.

Constraints

  • All values in input are integers.
  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 3 \times 10^5
  • 1 \leq a_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N M
a_1 a_2 \cdots a_M

Output

Print M lines. The i-th line should contain an integer representing the child who will have the i-th plate, or -1 if no child will have the plate.

Sample Input 1

2 5
5 3 2 4 8

Sample Output 1

1
2
-1
2
1
  • First, the conveyer belt conveys a plate with the deliciousness of 5.
    • When the plate is passing in front of Child 1, he has never had a plate, so he gets it.
  • Second, the conveyer belt conveys a plate with the deliciousness of 3.
    • When the plate is passing in front of Child 1, its deliciousness is not greater than that of the plate he has had, so he ignores it.
    • When the plate is passing in front of Child 2, she has never had a plate, so she gets it.
  • Third, the conveyer belt conveys a plate with the deliciousness of 2.
    • When the plate is passing in front of Child 1, its deliciousness is not greater than those of the plates he has had, so he ignores it.
    • When the plate is passing in front of Child 2, its deliciousness is not greater than those of the plates she has had, so she ignores it.
    • When the plate is passing in front of Child 3, he has never had a plate, so he gets this plate.
  • Fourth, the conveyer belt conveys a plate with the deliciousness of 4.
    • When the plate is passing in front of Child 1, its deliciousness is not greater than those of the plates he has had, so he ignores it.
    • When the plate is passing in front of Child 2, its deliciousness is greater than those of the plates she has had, so she gets it.
  • Fifth, the conveyer belt conveys a plate with the deliciousness of 8.
    • When the plate is passing in front of Child 1, its deliciousness is greater than those of the plates he has had, so he gets it.

Sample Input 2

5 10
13 16 6 15 10 18 13 17 11 3

Sample Output 2

1
1
2
2
3
1
3
2
4
5

Sample Input 3

10 30
35 23 43 33 38 25 22 39 22 6 41 1 15 41 3 20 50 17 25 14 1 22 5 10 34 38 1 12 15 1

Sample Output 3

1
2
1
2
2
3
4
2
5
6
2
7
6
3
7
6
1
7
4
8
9
6
9
9
4
4
10
9
8
-1