AT_abc476_c.Third Largest Number

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.

给定一个不小于 $3$ 的整数 $N$，以及一个长度为 $N$ 的正整数序列 $A=(A_1,A_2,\ldots,A_N)$。

对每个 $k=3,4,\ldots,N$，求解以下问题：

• 将 $A_1,A_2,\ldots,A_k$ 按降序排序后，找出从前往后数的第三个值。

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

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

输入从标准输入中按以下格式给出：

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

Output $N-2$ lines.

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

输出 $N-2$ 行。

第 $i$ 行（$1\le i\le N-2$）应包含 $k=i+2$ 时的答案。

Sample 1 Explanation:

• 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.

Constraints

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

样例 1 解释：

• 当 $k=3$ 时：将 $A_1,A_2,A_3$ 按降序排序得到 $2,1,1$，从前数第 3 个值为 $1$，因此在第一行输出 $1$。
• 当 $k=4$ 时：将 $A_1,A_2,A_3,A_4$ 按降序排序得到 $2,2,1,1$，从前数第 3 个值为 $1$，因此在第二行输出 $1$。
• 当 $k=5$ 时：将 $A_1,A_2,A_3,A_4,A_5$ 按降序排序得到 $3,2,2,1,1$，从前数第 3 个值为 $2$，因此在第三行输出 $2$。

限制条件

• $3\le N\le 5\times 10^5$
• $1\le A_i\le 10^9$
• 所有输入值均为整数。