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

이 문제에서는 부모의 값이 두 자식의 값보다 크거나 같은 최대 힙을 사용한다. 배열의 \(1\)번 원소를 힙의 루트로 사용하며, \(k\)번 원소의 왼쪽 자식은 \(2k\)번, 오른쪽 자식은 \(2k+1\)번 원소이다.

먼저 주어진 배열을 최대 힙으로 만든다. 이후 힙의 루트에 있는 최댓값을 힙의 마지막 원소와 교환하고, 힙의 크기를 하나 줄인 뒤 남은 힙을 다시 최대 힙으로 만든다. 힙에서 제외된 뒤쪽 원소들은 이미 정렬된 상태가 된다.

의사 코드

아래로_내리기(k, H)
    left = 2 * k

    if left > H
        함수를 종료한다.

    child = left
    right = left + 1

    if right <= H이고 A[child] < A[right]
        child = right

    if A[k] < A[child]
        A[k]와 A[child]를 교환한다.
        아래로_내리기(child, H)

힙_만들기()
    for k = N / 2의 몫부터 1까지 1씩 감소시키며 반복
        아래로_내리기(k, N)

힙_정렬()
    힙_만들기()
    배열 A의 모든 원소를 출력한다.

    H = N
    for i = N부터 2까지 1씩 감소시키며 반복
        A[1]과 A[i]를 교환한다.
        H = H - 1
        아래로_내리기(1, H)
        배열 A의 모든 원소를 출력한다.

처음에는 힙_정렬()을 호출한다. 두 자식의 값이 같으면 왼쪽 자식을 선택한다.

최대 힙을 완성한 직후의 배열을 먼저 출력한다. 이후 최댓값을 정렬된 위치로 옮기고 남은 힙을 복구할 때마다 배열을 출력한다. 따라서 총 \(N\)개의 줄을 출력해야 한다.

입력

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

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

출력

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

제한 사항

• \(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

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

예제 설명 1

먼저 주어진 배열을 최대 힙으로 만들면 5 4 2 3 1이 된다. 이후 루트의 최댓값을 현재 힙의 마지막 원소와 교환하고 남은 힙을 복구한다. 같은 과정을 반복하면 마지막 단계에서 배열 전체가 오름차순으로 정렬된다.