Background

除了得到排序结果，我们还可以观察排序过程中的一些信息，比如一共发生了多少次交换。

Description

给定一个长度为 n 的整数数组，请你使用标准的升序冒泡排序将它排好。

每当两个相邻元素发生一次交换，交换次数就加 1。请在排序结束后输出排好序的数组，以及总交换次数。

Format

Input

第 1 行：1 个整数 n，表示数组长度。

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

Output

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

第 2 行输出 1 个整数，表示冒泡排序过程中实际发生的交换次数。

Samples

4
4 3 2 1

1 2 3 4
6

Hint

只有真正执行交换时才计数。如果两个相邻元素已经满足顺序要求，就不要把这次比较算成交换。

Limitation

1s, 256MiB for each test case.