题目描述

给定一个不小于 $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 ... A_N

输出格式

输出 $N-2$ 行。

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

输入示例 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 \sim A_4$ 降序排列为 $2, 2, 1, 1$，第 $3$ 个是 $1$；
• $k = 5$：$A_1 \sim A_5$ 降序排列为 $3, 2, 2, 1, 1$，第 $3$ 个是 $2$。

注意是按「元素个数」数到第 $3$ 个，相同的值要重复计数，不是「第 $3$ 大的不同值」。$k=4$ 时有两个 $2$，它们各占一个位置。

输入示例 2

10
1 1 1 3 2 5 4 3 6 5

输出示例 2

1
1
1
2
3
3
4
5

示例 2 说明

开头三个都是 $1$，所以前几行的答案都是 $1$。随着更大的数不断加入，答案单调上升。这一点是普遍规律：加入新元素只可能让第 $3$ 大变大或不变，绝不会变小。

输入示例 3

10
11 9 1 3 17 19 10 19 17 3

输出示例 3

1
3
9
11
11
17
17
17

示例 3 说明

序列中出现了重复的 $19$ 和 $17$。$k = 8$ 时前 $8$ 个数降序为 $19, 19, 17, 11, 10, 9, 3, 1$，第 $3$ 个是 $17$——两个 $19$ 各占一位，这正是「重复计数」的体现。

约束条件

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