Background

有些数组并不需要做满所有趟冒泡，就已经完全有序了。

Description

给定一个长度为 n 的整数数组，请你按升序进行冒泡排序。

如果某一趟冒泡中一次交换也没有发生，说明数组已经有序，此时应立即结束排序。

请输出最终排好序的数组，以及实际执行了多少趟冒泡。

Format

Input

第 1 行：1 个整数 n，表示数组长度，保证 n >= 2。

第 2 行：n 个整数，表示数组中的元素。

Output

第 1 行输出排序后的数组。

第 2 行输出 1 个整数，表示实际执行的冒泡趟数。

Samples

5
1 2 3 5 4

1 2 3 4 5
2

Hint

如果一开始数组就是有序的，也要先完成第 1 趟检查；只是这一趟不会发生交换，随后立刻结束。

Limitation

1s, 256MiB for each test case.