题目描述

译自 ROIR 2016 Day1 T1. Призы

彼得参与了一个抽奖活动，活动中共有 $n$ 个奖品，编号从 $1$ 到 $n$。

根据比赛结果，参赛者可以获得 $2$ 到 $n$ 分。如果参赛者获得 $k$ 分，他将获得编号从 $1$ 到 $k$ 的某个奖品。在参赛者选择奖品之前，比赛主持人会从列表中移除一个奖品。之后，参赛者可以从剩余的 $k-1$ 个奖品中任意选择一个。

奖品列表已为彼得所知。彼得为每个奖品确定了其价值，第 $i$ 个奖品的价值为整数 $a_i$。

你的任务是编写一个程序，根据给定的奖品价值，确定对于每个从 $2$ 到 $n$ 的 $k$，如果彼得在比赛中获得 $k$ 分，则他能保证获得的奖品的最大价值是多少。

输入格式

输入文件的第一行包含一个整数 $n$ $(2 \leq n \leq 100000)$。第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ $(1 \leq a_i \leq 10^{9})$。

输出格式

输出文件应包含一行，其中包含 $n-1$ 个整数：对于每个从 $2$ 到 $n$ 的 $k$，输出如果彼得获得 $k$ 分时，他能获得的奖品的最大价值。

5
1 3 4 2 5

1 3 3 4

数据范围与提示

详细子任务附加限制及分值如下表所示：