U244852 插入排序模板题

插入排序，时间复杂度（平均）$O(n^2)$，时间复杂度（最坏）$O(n^2)$，时间复杂度（最好）$O(n)$，空间复杂度$O(1)$，稳定性：稳定 插入排序（$Insertion-Sort$）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序的数据，在已排序序列中从后向前扫描，找到相应位置并插入。

给你一个正整数$n$和$n$个正整数$a_1$~$a_n$（无序），请将其用**插入排序**排序，并输出该数组排序后的结果。

第一行：$n$ 第二行：$a_i$~$a_n$

第一行：排序后的$a_1$~$a_n$

$10 \leq n \leq 800$ $1 \leq a_i \leq 10^4$