Description

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

Format

Input

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

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

Output

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

Samples

5
2 5 4 1 3

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

Sample 1 explain

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

• 第一次在 $a_{2\sim 5}$ 中最小的为 $a_4$，让它和 $a_1$ 交换，此时序列变为 $a=[1, 5, 4, 2, 3]$
• 第二次在 $a_{3\sim 5}$ 中最小的为 $a_4$，让它和 $a_2$ 交换，此时序列变为 $a=[1, 2, 4, 5, 3]$
• 第三次在 $a_{4\sim 5}$ 中最小的为 $a_5$，让它和 $a_3$ 交换，此时序列变为 $a=[1, 2, 3, 5, 4]$
• 第四次在 $a_{5\sim 5}$ 中最小的为 $a_5$，让它和 $a_4$ 交换，此时序列变为 $a=[1, 2, 3, 4, 5]$

可以证明 $n$ 个元素的序列只需要经过 $n-1$ 轮即可成功排序。

Limitation

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