题目描述

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

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

• 将 $A_1, A_2, \ldots, A_k$ 按降序（从大到小）排序后，求从前往后数第 $3$ 个元素的值。

输入格式

输入从标准输入中给出，格式如下：

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

输出格式

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

数据范围

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

样例

样例输入 1

5
1 2 1 2 3

样例输出 1

1
1
2

样例解释 1：

• $k=3$ 时：$A_1, A_2, A_3$ 降序排序后为 $2, 1, 1$，第 3 个值为 $1$。
• $k=4$ 时：$A_1, A_2, A_3, A_4$ 降序排序后为 $2, 2, 1, 1$，第 3 个值为 $1$。
• $k=5$ 时：$A_1, A_2, A_3, A_4, A_5$ 降序排序后为 $3, 2, 2, 1, 1$，第 3 个值为 $2$。

样例输入 2

10
1 1 1 3 2 5 4 3 6 5

样例输出 2

1
1
1
2
3
3
4
5

样例输入 3

10
11 9 1 3 17 19 10 19 17 3

样例输出 3

1
3
9
11
11
17
17
17