题目描述

使用冒泡排序对输入的 $n$ 个数字进行升序排列。

注意：

• 两个相等的数字不应进行交换操作
• 当排序过程中，数列已经有序时，应停止后续多余的排序操作
• 如果原始数列本身是升序的，则不输出

依次输出每趟排序的结果。

输入格式

第一行一个数 $n$,

第二行 $n$ 个待排序的数字$a_i$。

输出格式

若干行，每行 $n$ 个用空格隔开的数字，表示每一趟排序的结果。

样例

5
4 1 2 5 3

1 2 4 3 5
1 2 3 4 5

3
1 3 5

说明/提示

对 100% 数据，$1 \le n \le 1000, 1 \le a_i \le 10^5$。