题目描述

春节来临，你和朋友们一起玩起了扑克牌。

每次抓起一张牌，你会按从小到大的顺序，将这张扑克牌，插入到正确的位置，使得牌面保持从小到大的顺序。

具体抓牌时，你会先把这张牌放到最后一张牌的右侧，然后观察牌面顺序是否满足从小到大的顺序。如果不满足，再将这张牌插入到正确的位置上，使得所有的牌面保持从小到大的顺序。

这让你不禁想起了编程课上学习的插入排序。于是你的脑袋中不自觉的演练起了插入排序的过程。

假设有 5个互不相等的整数：3 1 5 4 2。如果前 4 个数已经通过插入排序排好序了。

那么，插入 2 的过程将会是这样的：

1. 初始状态下，先把 2 放到末尾，得到：1 3 4 5 2。
2. 将 2 存入临时变量 t 中。
3. 用指针 j 指向 2 的前一个元素 5，然后判断 t 和 a[j] 的大小关系，以决定a[j]是否需要后移。如果 a[j]>t，则需要让a[j] 后移到 a[j+1] 的位置，从而得到 1 3 4 5 5。
4. 接下来，将指针 j 继续前移，判断 a[j]>t 成立，因此将 a[j]后移到a[j+1] 的位置，得到 1 3 4 4 5。
5. 继续将指针j 前移，判断 a[j]>t 成立，因此将 a[j] 后移到a[j+1] 的位置，得到 1 3 3 4 5。
6. 继续将指针 j前移，判断 a[j]>t 不成立，因此将 t放到 a[j+1]的位置，得到 1 2 3 4 5。

完美的插入排序的过程！

现在输入 N 个互不相等的整数，请编程模拟插入排序的全过程。你可以通过样例 1 的输出，更加形象的了解插入排序的过程。

​请注意输出格式​，除了每个元素刚插入时输出 Insert element[i]: 以外，其余每行输出前，请先输出 2 个空格。

输入

第一行输入一个正整数 N，表示读入数据的总数。

第二行输入 N 个互不相等的整数，以空格隔开。

输出

输出格式请参照样例 11 的输出格式。

样例

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

4
4 3 2 1

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

说明

数据规模和约定

对于 100%* 的数据，满足 N≤100，整数元素在 int范围。