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

이 문제에서 사용하는 선택 정렬은 아직 정렬되지 않은 구간에서 최댓값을 찾은 뒤, 그 값을 구간의 맨 뒤에 있는 값과 교환한다. 이 과정을 반복하면 큰 값부터 배열의 뒤쪽에 차례대로 놓이게 된다.

의사 코드

for i = N부터 2까지 1씩 감소시키며 반복
    maxIndex = 1
    for j = 2부터 i까지
        if A[j] > A[maxIndex]
            maxIndex = j
    A[maxIndex]와 A[i]를 교환한다.
    배열 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

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

예제 설명 1

첫 번째 단계에서는 최댓값 \(5\)를 찾아 다섯 번째 원소와 교환한다. 두 번째 단계에서 정렬되지 않은 구간의 최댓값 \(4\)는 이미 해당 구간의 맨 뒤에 있으므로 배열의 모습이 바뀌지 않는다. 이후에도 같은 과정을 반복하여 총 네 단계의 배열을 모두 출력한다.