Description

插入排序基本思想是每一步将一个待排序的记录，插入到前面已经排好序的有序序列中去，直到插完所有元素为止。

假设前面 $n-1$(其中 $n>2$)个数已经是排好顺序的，现将第 n 个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的。

按照此法对所有元素进行插入，直到整个序列排为有序的过程，称为插入排序。

输入$N$个整数，将它们从小到大排队后输出

输入$N$个整数，将它们从小到大排队后输出。

Input Format

第一行输入一个整数$N$

第二行输入$N$个整数$a_i$

【约定】 $1≤N≤1000，0≤a_i≤10^9$ ​

Output Format

输出排好序的$N$个数。

5
1 4 2 3 5

1 2 3 4 5