题目背景

翻译自 ROIR 2016 D1T1。

题目描述

Petya 参加了一个比赛，在这个比赛中将会抽取 $n$ 个奖品。奖品编号从 $1$ 到 $n$。

根据比赛结果，参赛者可以获得 $2$ 到 $n$ 之间的分数。如果参赛者获得了 $k$ 分，那么他将从编号 $1$ 到 $k$ 的奖品中获得一个奖品。比赛主持人在参赛者选择奖品之前，会从奖品列表中删除一个奖品。然后，参赛者可以从剩下的 $k - 1$ 个奖品中选择一个。

Petya 知道所有奖品的价值，第 $i$ 个奖品的价值为 $a_i$。

对于每个 $2\le k\le n$，你需要求出如果 Petya 获得了 $k$ 分，他一定能得到的最大奖品价值是多少。

输入格式

第一行输入一个整数 $n$（$2 \le n \le 100000$）。

第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n$（$1\le a_i\le10^9$）。

输出格式

输出一行 $n-1$ 个整数，其中第 $k-1$ 个整数表示如果 Petya 获得了 $k$ 分，他一定能得到的最大奖品价值。

5
1 3 4 2 5

1 3 3 4

提示