Олимпиадный тренинг

Задача 37170. Сортировка вставками


Требуется отсортировать массив по неубыванию методом "вставок".

Входные данные 
В первой строке вводится одно натуральное число N, не превосходящее 1000 – размер массива. Во второй строке задаются N чисел – элементы массива (целые числа, не превосходящие по модулю 1000).

Выходные данные 
Вывести получившийся массив.
 
Пример
Входные данные Выходные данные
1 5
5 4 3 2 1
1 2 3 4 5

Запрещенные операторы:sort