题目描述

给定含有 $n$ 个整数的序列，要求对这个序列进行从小到大的插入排序。并且输出排序过程。

输入格式

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

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

输出格式

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

输入输出样例

5
3 8 4 9 7

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