#80Medium

Bubble sort

Time: 1 s · Memory: 256 MB

Arrays

Statement

Sort the array in increasing order with bubble sort: compare neighbouring elements and swap them if the left one is greater; repeat such a pass over the array $n - 1$ times.

Print the sorted array and the number of swaps the algorithm made.

Input format

The first line contains $n$ ( $1 \le n \le 1000$ ). The second line contains $n$ integers ( $|a_i| \le 10^9$ ).

Output format

The first line contains the sorted array. The second line contains the number of swaps.

Examples

Input

5
4 6 2 1 7

Output

1 2 4 6 7
5

Input

3
1 2 3

Output

1 2 3
0

Note

Swap only when the left element is strictly greater — equal elements stay in place, otherwise the swap count comes out too large. In the first example: 1 2 4 6 7 with $5$ swaps.

For $n = 1000$ there are about $5 \cdot 10^5$ swaps — two nested loops fit into the time limit.

Bubble sort

Time: 1 s · Memory: 256 MB

Arrays

Statement

Sort the array in increasing order with bubble sort: compare neighbouring elements and swap them if the left one is greater; repeat such a pass over the array $n - 1$ times.

Print the sorted array and the number of swaps the algorithm made.

Input format

The first line contains $n$ ( $1 \le n \le 1000$ ). The second line contains $n$ integers ( $|a_i| \le 10^9$ ).

Output format

The first line contains the sorted array. The second line contains the number of swaps.

Examples

Input

5
4 6 2 1 7

Output

1 2 4 6 7
5

Input

3
1 2 3

Output

1 2 3
0

Note

Swap only when the left element is strictly greater — equal elements stay in place, otherwise the swap count comes out too large. In the first example: 1 2 4 6 7 with $5$ swaps.

For $n = 1000$ there are about $5 \cdot 10^5$ swaps — two nested loops fit into the time limit.