题目描述

给定一个不小于 $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$ 时的答案。

5
1 2 1 2 3

1
1
2

• 对于 $k=3$：将 $A_1,A_2,A_3$ 按从大到小排序得到 $2,1,1$。从前往后数第 $3$ 个值是 $1$，因此在第 $1$ 行输出 $1$。
• 对于 $k=4$：将 $A_1,A_2,A_3,A_4$ 按从大到小排序得到 $2,2,1,1$。从前往后数第 $3$ 个值是 $1$，因此在第 $2$ 行输出 $1$。
• 对于 $k=5$：将 $A_1,A_2,A_3,A_4,A_5$ 按从大到小排序得到 $3,2,2,1,1$。从前往后数第 $3$ 个值是 $2$，因此在第 $3$ 行输出 $2$。

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

数据范围

• $3\le N\le 5\times 10^5$

• $1\le A_i\le 10^9$

• 所有输入值均为整数。

• 来源：AtCoder ABC 476 C

子任务设置

• 子任务 1（30 分）：$N \le 2000$。
• 子任务 2（70 分）：无特殊限制。