Problem Statement

You are given an integer $N$ not less than $3$ and a length-$N$ sequence of positive integers $A=(A_1,A_2,\ldots,A_N)$.

For each $k=3,4,\ldots,N$, solve the following problem:

• When $A_1,A_2,\ldots,A_k$ are sorted in descending order, find the third value from the front.

Constraints

• $3\le N\le 5\times 10^5$
• $1\le A_i\le 10^9$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

• $N$
• $A_1$ $A_2$ $\ldots$ $A_N$

Output

Output $N-2$ lines.

The $i$-th line $(1\le i\le N-2)$ should contain the answer for $k=i+2$.

5
1 2 1 2 3

1
1
2

• For $k=3$: sorting $A_1,A_2,A_3$ in descending order gives $2,1,1$. The third value from the front is $1$, so output $1$ on the first line.
• For $k=4$: sorting $A_1,A_2,A_3,A_4$ in descending order gives $2,2,1,1$. The third value from the front is $1$, so output $1$ on the second line.
• For $k=5$: sorting $A_1,A_2,A_3,A_4,A_5$ in descending order gives $3,2,2,1,1$. The third value from the front is $2$, so output $2$ on the third line.

10
1 1 1 3 2 5 4 3 6 5

1
1
1
2
3
3
4
5

10
11 9 1 3 17 19 10 19 17 3

1
3
9
11
11
17
17
17

• Source: AtCoder ABC 476 C