Input

3
1 1

Output

1 1 2

Input

5
1 1 3 3

Output

1 1 1 2 3