题目描述

直接插入插排的基本思想是：当插入第i(i >= 1)时，前面的V[0]，V[1]，……，V[i-1]已经排好序。这时，用V[I]的排序码与V[i-1]，V[i-2]，…的排序码顺序进行比较，找到插入位置即将V[i]插入，原来位置上的元素向后顺移。

      在图一中给出了直接插入排序的过程。设在元素表中有n = 6个元素，为了使描述书简介直观，在图中只画出各元素的排序码。其中有两个排序码相同，前一个直接写为25，后一个标记为25*。假定其中V[0]，…，V[i-1]已经是一组有序的元素，V[i]，V[i+1]，……，V[n-1]是带插入的元素。排序过程从i = 1起，每执行完一趟之后i增加1，把第i各元素插入到前面有序的元素序列中去，使插入后的元素序列V[0]，V[1]，……，V[i-1]仍保持有序。

输入格式

多组测试数据，每组数据包含一个n(2≤n≤20)和一个长度为n的序列。

输出格式

对序列进行插入(Insert sort)排序，输出每轮排序后的结果，应该为n-1轮。每组测试数据后输出一个空行。

11
250 486 323 302 403 769 451 582 970 489 46
7
33 797 729 788 505 528 294

250 486 323 302 403 769 451 582 970 489 46 
250 323 486 302 403 769 451 582 970 489 46 
250 302 323 486 403 769 451 582 970 489 46 
250 302 323 403 486 769 451 582 970 489 46 
250 302 323 403 486 769 451 582 970 489 46 
250 302 323 403 451 486 769 582 970 489 46 
250 302 323 403 451 486 582 769 970 489 46 
250 302 323 403 451 486 582 769 970 489 46 
250 302 323 403 451 486 489 582 769 970 46 
46 250 302 323 403 451 486 489 582 769 970

33 797 729 788 505 528 294 
33 729 797 788 505 528 294 
33 729 788 797 505 528 294 
33 505 729 788 797 528 294 
33 505 528 729 788 797 294 
33 294 505 528 729 788 797