题目描述

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

输入格式

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

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

输出格式

每次交换后的数列，每个数字之间用空格隔开，具体格式见样例。注意输出文字后面的 ： 是中文状态下的。

输入输出样例

8
8 4 5 7 1 3 6 2

归并：8 4 
排序：4 8 
归并：5 7 
排序：5 7 
归并：4 8 5 7 
排序：4 5 7 8 
归并：1 3 
排序：1 3 
归并：6 2 
排序：2 6 
归并：1 3 2 6 
排序：1 2 3 6 
归并：4 5 7 8 1 2 3 6 
排序：1 2 3 4 5 6 7 8