JOI-kun and the Go Stones

JOI-kun has (N) go stones. The stones are numbered from (1) to (N). Each stone's color is an integer between (1) and (10^9) (inclusive), and initially, the color of Stone (i) is (A_i).

JOI-kun will perform (N) operations. In the (i)-th operation, he does the following:
1. Place Stone (i) immediately to the right of Stone (i-1) (for (i=1), simply place Stone 1 on the table).
2. If there is at least one stone among Stones (1,2,\dots,i-1) whose current color is the same as Stone (i), let (j) be the maximum index for which this holds. Then, repaint all stones numbered (j+1,j+2,\dots,i-1) with the color (A_i).

Your task is to determine the final colors of all the stones after all operations are performed.

inputFormat

The first line contains an integer (N).
The second line contains (N) integers (A_1, A_2, \dots, A_N) separated by spaces.

outputFormat

Output a single line with (N) integers representing the final colors of the stones, separated by spaces.

sample

4
1 2 1 3

1 1 1 3