题目描述

排序，顾名思义，是将若干个元素按其大小关系排出一个顺序。形式化描述如下：有 $n$ 个元素 $a_1, a_2, \dots, a_n$，从小到大排序就是将它们排成一个新顺序，且 $a_{i_1} \le a_{i_2} \le \dots \le a_{i_n}$。

插入排序是一种基础的排序算法，其过程如下：从第一个元素开始，该元素可以认为已经被排序。取出下一个元素，在已经排序的元素序列中从后向前扫描，如果该元素（已排序）大于新元素，则将该元素移到下一位置，重复这个过程，直到找到已排序的元素小于或者等于新元素的位置，将新元素插入到该位置后。重复此过程，直到所有元素处理完毕。

例如，输入 $5$ 个整数 $3,1,5,4,2$，插入排序的全过程如下面的输出样例所示。

现在，输入 $n$ 个整数，根据以上算法，输出插入排序的全过程。

输入格式

第一行一个正整数 $n$，表示元素个数。

第二行为 $n$ 个整数，以空格隔开。

输出格式

输出插入排序的全过程，有 $n$ 个部分，每个部分开头为 Insert element[i]:，其中 $i$ 为第几个元素。然后对于每一个部分，输出该元素在插入排序过程中的每一步产生的新序列，初始时的序列以 Init: 打头，然后每一步后移数组元素后的元素序列以 Move back: 打头，最后得到的最终结果序列以 Final: 打头。序列元素间以一个空格隔开。

每一个部分的 Insert element[i]: 之后的每一步的输出行之前要缩进两格，即输出两个空格。

样例

5
3 1 5 4 2

Insert element[1]:
Init:3
Final:3
Insert element[2]:
Init:3 1
Move back:3 3
Final:1 3
Insert element[3]:
Init:1 3 5
Final:1 3 5
Insert element[4]:
Init:1 3 5 4
Move back:1 3 5 5
Final:1 3 4 5
Insert element[5]:
Init:1 3 4 5 2
Move back:1 3 4 5 5
Move back:1 3 4 4 5
Move back:1 3 3 4 5
Final:1 2 3 4 5

数据范围与提示

对于 $100\%$ 的数据，$1 \le n \le 100$。

来源

蓝桥杯练习系统