삽입 정렬을 해볼까

삽입 정렬은 배열의 요소를 앞에서부터 차례대로 이미 정렬된 배열과 비교하여 자신의 위치를 찾아 삽입해 정렬하는 알고리즘이다. 아래 그림은 배열 $[3\,1\,4\,1\,5\,9\,2\,6\, 5\, 3\, 5]$를 삽입 정렬하는 과정을 나타낸 것이다.

길이 $n$의 배열 $a$가 주어질 때 $t$번째 원소까지 올바른 위치에 삽입한 배열을 구해보자.

첫 번째 줄에 배열 $a$의 길이 $n$과 $t$가 주어진다. ($1 \leq n \leq 10^6; 1 \leq t \leq n$)

두 번째 줄에 $a$의 원소 $n$개가 공백으로 구분되어 주어진다. ($1\leq a_i \leq 10^{9}$)

주어지는 모든 수는 정수이다.

$t$번째 원소까지 올바른 위치에 삽입한 배열을 공백으로 구분하여 출력한다.

충분히 빠른 입출력 방식을 사용하지 않으면 시간 초과를 받을 수 있다.

예를 들어 C++의 cin/cout을 사용할 때에는 입력받기 전에 cin.tie(NULL);을 사용하고, Python에서는 input() 대신 sys.stdin.readline()을 사용하는 것을 권장한다.