Page not loading? Try clicking here.
Placeholder

#1146

Selection Sort 1s 32MB

Problems

Selection sort is an internal sorting algorithm that works as follows:

  1. Find the minimum value in the given sequence (if there are multiple identical values, choose the first one).

  2. Swap the found minimum value with the value at the front.

  3. Exclude the first value from the sequence, and repeat the same process on the remaining sequence for a total of N-1 times.

Given a sequence of N numbers, sort it using the above method.


Input

The first line contains the length of the sequence N (4≤N≤100).

The second line contains N integers between 0 and 100 inclusive.


Output

Excluding the initial state, print the sequence after each step of the selection sort.

Follow the output format as described (each step on a separate line, numbers separated by spaces).


Example 

5

6 4 8 3 1
1 4 8 3 6

1 3 8 4 6

1 3 4 8 6

1 3 4 6 8


Source

JUNGOL

You must sign in to write code.