时空限制

1S/512M

题目描述

$n$ 个人排队，从前往后的第 $i$ 个人身高为 $h_i$。

进行 $n$ 轮调整，第 $i$ 轮调整中：

• 如果第 $i$ 个人发现他前面的所有人身高都不高于他，则所有人位置不变；
• 否则，找到身高比他高的人中位置最靠前那个，两人交换位置。

求 $n$ 轮调整结束后从前往后每个人的身高。

格式

输入格式

第一行包含一个整数 $n$，表示人数。

第二行包含 $n$ 个整数 $h_i$，表示每个人的身高。

输出格式

输出 $n$ 个整数，分别表示 $n$ 轮调整结束后从前往后每个人的身高。

样例

样例输入 #1

5
5 4 2 3 1

样例输出 #1

1 3 4 5 2

样例解释 #1

第 $1$ 轮调整后，从前往后每个人的身高为：$\{5,4,2,3,1\}$。

第 $2$ 轮调整后，从前往后每个人的身高为：$\{4,5,2,3,1\}$。

第 $3$ 轮调整后，从前往后每个人的身高为：$\{2,5,4,3,1\}$。

第 $4$ 轮调整后，从前往后每个人的身高为：$\{2,3,4,5,1\}$。

第 $5$ 轮调整后，从前往后每个人的身高为：$\{1,3,4,5,2\}$。

样例输入 #2

6
3 2 1 4 3 4 

样例输出 #2

1 3 2 3 4 4

数据规模

对于 $100\%$ 的数据，$1\leq n\leq 3000$，$1\leq h_i\leq 1000$。