Problem Description

$ N $ children who have never eaten sushi before come to a rotating sushi restaurant. Each child is numbered from $1, 2, 3, \ldots, N$.

$ M $ pieces of sushi will flow by in order. The deliciousness of the $ i $-th sushi is $ a_i $. The sushi will pass in front of the children in the order $1, 2, 3, \ldots, N$.

Each child will only take and eat a sushi that passes in front of them if it meets one of the following conditions. Otherwise, they will do nothing:

• They have not eaten any sushi yet.
• The deliciousness of the sushi is greater than any sushi they have eaten before.

For each sushi, determine which child will eat it.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ a_1 $ $ a_2 $ $\cdots$ $ a_M $

Output Format

Output $ M $ lines. The $ i $-th line should contain the number of the child who eats the $ i $-th sushi. If no child eats it, output -1.

Sample Input and Output

Sample Input #1

2 5
5 3 2 4 8

Sample Output #1

1
2
-1
2
1

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

Notes/Hints

Constraints

• All given inputs are integers.
• $1 \leq N \leq 10^5$
• $1 \leq M \leq 3 \times 10^5$
• $1 \leq a_i \leq 10^9$

Sample Explanation 1

• The 1st sushi with deliciousness 5 flows by.
• When it passes child 1, child 1 has not eaten any sushi yet, so child 1 takes and eats this sushi.
• The 2nd sushi with deliciousness 3 flows by.
• When it passes child 1, child 1 has eaten a sushi with deliciousness 5, so child 1 does not take this sushi.
• When it passes child 2, child 2 has not eaten any sushi yet, so child 2 takes and eats this sushi.
• The 3rd sushi with deliciousness 2 flows by.
• When it passes child 1, child 1 has eaten a sushi with deliciousness 5, so child 1 does not take this sushi.
• When it passes child 2, child 2 has eaten a sushi with deliciousness 3, so child 2 does not take this sushi.
• The 4th sushi with deliciousness 4 flows by.
• When it passes child 1, child 1 has eaten a sushi with deliciousness 5, so child 1 does not take this sushi.
• When it passes child 2, this sushi has greater deliciousness than any sushi child 2 has eaten before, so child 2 takes and eats this sushi.
• The 5th sushi with deliciousness 8 flows by.
• When it passes child 1, this sushi has greater deliciousness than any sushi child 1 has eaten before, so child 1 takes and eats this sushi.

见题面 Input 部分

见题面 Output 部分