### 问题描述 给定一个序列 $a[1], a[2], …, a[n]$ ，对于 $3 \leq i \leq n$，请求出前 $i$ 个数中的第 $3$ 小值。 ### 输入格式 输入的第一行包含一个整数 $n$ ，表示序列的长度。 第二行包含 $n$ 个整数，相邻的整数之间使用一个空格分隔，表示给定的序列。 ### 输出格式 输出一行包含 $n - 2$ 个整数，相邻两个数之间使用一个空格分隔，第 $i$ 个整数表示 $a[1], a[2], ..., a[i+2]$ 中的第 $3$ 小值。 ### 样例输入 ``` 9 9 9 8 2 4 4 3 5 3 ``` ### 样例输出 ``` 9 9 8 4 4 4 3 ``` ### 数据范围 对于 $50$% 的评测用例，$1 \leq n \leq 1000$，$0 \leq a[i] \leq 10000$。 对于所有评测用例，$1 \leq n \leq 10^5$，$0 \leq a[i] \leq 10^6$。