Background

学会完整写出冒泡排序，是一维数组排序中的基础能力。

Description

给定一个长度为 n $(n \leq 100)$的整数数组，请你使用冒泡排序把它按从小到大的顺序排列，并输出排序后的结果。

在冒泡排序中，需要进行多趟比较。每一趟都从左到右扫描，把当前较大的元素逐步交换到后面。

Format

Input

第 1 行：1 个整数 n，表示数组长度。

第 2 行：n 个整数，表示数组中的元素。

Output

输出 1 行，包含 n 个整数，表示按升序排序后的数组。

Samples

6
9 4 7 2 5 1

1 2 4 5 7 9

Hint

这是一道标准模板题。外层循环控制“做几趟”，内层循环控制“这一趟比较到哪里”。

Limitation

1s, 256MiB for each test case.