Description

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

Format

Input

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

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

Output

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

Samples

5
5 4 3 2 1

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

Sample 1 explain

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

• 第一轮冒泡把 $5$ 冒到倒数第一的位置，此时 $a=[4,3,2,1,5]$
• 第二轮冒泡把 $4$ 冒到倒数第二的位置，此时 $a=[3,2,1,4,5]$
• 第三轮冒泡把 $3$ 冒到倒数第三的位置，此时 $a=[2,1,3,4,5]$
• 第四轮冒泡把 $2$ 冒到倒数第四的位置，此时 $a=[1,2,3,4,5]$

Limitation

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