题目描述

小 S 同学已经在课堂上学习了快速排序，接下去打算出题考考你，给出含有 $n$ 个整数的序列，要求对这个序列进行从小到大进行快速排序。并且按要求输出排序过程。

输入格式

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

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

输出格式

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

输入输出样例

10
6 1 2 7 9 3 4 5 10 8

第1次6归位
3 1 2 5 4 6 9 7 10 8
第2次3归位
2 1 3 5 4 6 9 7 10 8
第3次2归位
1 2 3 5 4 6 9 7 10 8
第4次1归位
1 2 3 5 4 6 9 7 10 8
第5次5归位
1 2 3 4 5 6 9 7 10 8
第6次4归位
1 2 3 4 5 6 9 7 10 8
第7次9归位
1 2 3 4 5 6 8 7 9 10
第8次8归位
1 2 3 4 5 6 7 8 9 10
第9次7归位
1 2 3 4 5 6 7 8 9 10
第10次10归位
1 2 3 4 5 6 7 8 9 10