Description

输入一个数字 $n$ 和 $n$ 个数字，请你使用插入排序完成从小到大排序的过程。

Format

Input

第一行输入一个整数 $n$

接下来一行输入 $n$ 个整数 $a_1,a_2,\cdots,a_n$

Output

输出一共输出 $n$ 行，分别输出每一次插入排序后的结果。具体可以参考样例解释。

Samples

5
5 4 3 2 1

5 4 3 2 1
4 5 3 2 1
3 4 5 2 1
2 3 4 5 1
1 2 3 4 5

Sample 1 explain

初始 a = [5, 4, 3, 2, 1]

• 从未排序集合拿出 $5$，插入到已排序集合，此时已排序集合为 $5$，未排序集合为 $4,3,2,1$
• 从未排序集合拿出 $4$，插入到已排序集合，此时已排序集合为 $4,5$，未排序集合为 $3,2,1$
• 从未排序集合拿出 $3$，插入到已排序集合，此时已排序集合为 $3,4,5$，未排序集合为 $2,1$
• 从未排序集合拿出 $2$，插入到已排序集合，此时已排序集合为 $2,3,4,5$，未排序集合为 $1$
• 从未排序集合拿出 $1$，插入到已排序集合，此时已排序集合为 $1,2,3,4,5$，未排序集合为空。

Limitation

$1\leq n\leq 10^3,1\leq a_i\leq 10^3$