Description

读入若干个数，使用插入排序算法将它们按照从小到大的顺序存储，输出排序后的结果以及排序过程中数据移动的次数。

Format

Input

第一行$n(n \leqslant 1000)$，$n$ 个元素

第二行$n$个整数

Output

第一行为排序后的结果，各个数之间以空格分隔；

第二行为一个整数，表示排序过程中数据移动的次数。

Samples

7
12 15 9 20 6 31 24

6 9 12 15 20 24 31
7