Input

5
1 1 1 1 1

Output

1 1 1 1 1

Input

5
1 6 4 2 8

Output

1 5 3 1 8