Background

冒泡排序并不是一下子就把整个数组排好，而是一趟一趟地进行。

Description

给定一个长度为 n 的整数数组，请你只进行 1 趟从左到右的冒泡操作，按升序排序的规则处理：如果相邻两个数前面的更大，就交换它们。

完成这一趟后，输出数组的状态。

Format

Input

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

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

Output

输出 1 行，包含 n 个整数，表示做完 1 趟冒泡后的数组。相邻两个数之间用 1 个空格隔开。

Samples

5
5 1 4 2 8

1 4 2 5 8

Hint

这道题只做 1 趟，不是把整个数组完全排好。1 趟结束后，当前数组中较大的数会被逐步“送”到后面。

Limitation

1s, 256MiB for each test case.