题目描述

给定含有 $n$ 个整数的序列，要求对这个序列进行从小到大的冒泡排序。注意，常规冒泡排序的过程中每一次都会去比较，但是有时候我们会发现数列已经是有序后，就不想要继续去进行排序操作来提升效率，现在请你优化。

输入格式

第一行包含一个正整数 $n$ （$2 \le n \le 100$），表示第二行序列中数字的个数。

第二行包含 $n$ 个整数，整数之间以一个空格分开。每个整数大于等于 $-1000$ 、 小于等于 $1000$ 。

输出格式

每次交换后的数列，每个数字之间用空格隔开，具体格式见样例。

输入输出样例

5
3 8 4 9 7

第1次
3 8 4 9 7
3 4 8 9 7
3 4 8 9 7
3 4 8 7 9
第2次
3 4 8 7 9
3 4 8 7 9
3 4 7 8 9
第3次
3 4 7 8 9
3 4 7 8 9

6
1 2 3 4 5 6

第1次
1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6