Insertion Sort Implementation

This problem requires you to implement the insertion sort algorithm to sort a sequence of integers in ascending order. The algorithm iterates through the list and inserts each element into its correct position relative to the previously sorted part of the list. The final output should display the sorted list.

Algorithm Overview:

The insertion sort algorithm works as follows:

• Start from the second element (index 1) and consider it as the key.
• Compare the key with all elements before it, shifting elements that are greater than the key to the right.
• Insert the key in the correct position.

Input is given via standard input and output must be written to standard output. Use the format specified in the input and output descriptions.

inputFormat

The input consists of two lines. The first line contains a single integer n (n ≥ 0) indicating the number of elements in the list. The second line contains n space-separated integers. If n is 0, the second line will be empty.

outputFormat

Output a single line containing the sorted list of integers in ascending order, with each integer separated by a single space. For an empty list, output nothing.## sample

5
1 2 3 4 5

1 2 3 4 5