Selection sort, pass by pass

Problem

A librarian puts book IDs in order using selection sort. In pass i (starting from the first position), she finds the smallest ID among positions i to the end and swaps it into position i. If it is already there, nothing is swapped.

Print the array after each of the n - 1 passes, then the number of real swaps.

Input, output and limits

Input: The first line has n. The second line has n integers: the book IDs.
Output: n - 1 lines, each the array after one pass, then a line Swaps: s.
Constraints: 1 ≤ n ≤ 100
-10^6 ≤ ID ≤ 10^6

Examples

Example

Input

5
64 25 12 22 11

Output

11 25 12 22 64
11 12 25 22 64
11 12 22 25 64
11 12 22 25 64
Swaps: 3

In pass 4, 25 is already in place, so it is not counted as a swap.

Hints

Try the problem first. Open one hint at a time.

Hint 1

For each i from 0 to n - 2, find minIndex, the index of the smallest value from i to n - 1.

Hint 2

Swap a[i] and a[minIndex] only if they are different indexes, and count that swap.

Hint 3

Use < (not <=) when looking for the smallest, so the first of equal values is chosen.

Write your Java code, run it on the examples and submit it to hidden tests.

Solve in the editor

All Java problems

Problem

Input, output and limits

Examples

Hints

More Arrays problems

Problem

Input, output and limits

Examples

Hints

More Arrays problems