정수로 이루어진 배열이 주어진다. 다음 의사 코드에 따라 삽입 정렬을 수행하고, 각 단계가 끝난 뒤의 배열을 출력해 보자.

삽입 정렬은 두 번째 원소부터 차례대로 확인한다. 현재 원소를 앞쪽의 정렬된 구간에서 알맞은 위치에 삽입하고, 그보다 큰 원소들은 오른쪽으로 한 칸씩 이동시킨다.

의사 코드

for i = 2부터 N까지
    value = A[i]
    j = i - 1

    while j >= 1이고 A[j] > value인 동안
        A[j + 1] = A[j]
        j = j - 1

    A[j + 1] = value
    배열 A의 모든 원소를 출력한다.

의사 코드의 바깥쪽 반복 한 번을 한 단계라고 한다. 현재 원소와 같은 값을 가진 원소는 이동시키지 않는다.

현재 원소가 이미 알맞은 위치에 있거나 배열이 도중에 이미 정렬되었더라도 반복을 중단하지 않고, 반드시 \(N-1\)단계를 모두 수행해야 한다.

입력

첫째 줄에 배열의 크기 \(N\)이 주어진다.

둘째 줄에 배열의 원소 \(A_1, A_2, \dots, A_N\)이 공백으로 구분되어 주어진다.

출력

각 단계가 끝날 때마다 배열의 모든 원소를 공백으로 구분하여 한 줄에 출력한다.

총 \(N-1\)개의 줄을 출력해야 한다.

제한 사항

• \(2 \le N \le 100\)
• \(-1,000,000,000 \le A_i \le 1,000,000,000\)

예제 입력 1

5
5 3 2 4 1

예제 출력 1

3 5 2 4 1
2 3 5 4 1
2 3 4 5 1
1 2 3 4 5

예제 설명 1

첫 번째 단계에서는 두 번째 원소 \(3\)을 앞쪽의 정렬된 구간에 삽입한다. 이후 각 단계에서 현재 원소를 앞쪽 구간의 알맞은 위치에 삽입하면 네 번째 단계가 끝난 뒤 배열 전체가 오름차순으로 정렬된다.