정수로 이루어진 배열이 주어진다. 다음 의사 코드에 따라 퀵 정렬을 수행하고, 분할이 끝날 때마다 그 결과를 출력해 보자.

퀵 정렬은 하나의 원소를 기준으로 정한 뒤, 기준 원소보다 작은 값과 그렇지 않은 값을 나누어 배치한다. 이후 기준 원소의 왼쪽 구간과 오른쪽 구간에도 같은 과정을 반복한다.

이 문제에서는 구간 \([p,r]\)의 마지막 원소 \(A_r\)를 기준 원소로 사용한다. 왼쪽 구간을 먼저 정렬한 뒤 오른쪽 구간을 정렬한다.

의사 코드

퀵_정렬(p, r)
    if p < r
        q = 분할(p, r)
        p, r, 콜론(:), A[p]부터 A[r]까지의 원소를 출력한다.
        퀵_정렬(p, q - 1)
        퀵_정렬(q + 1, r)

분할(p, r)
    x = A[r]
    i = p - 1

    for j = p부터 r - 1까지
        if A[j] < x
            i = i + 1
            A[i]와 A[j]를 교환한다.

    A[i + 1]과 A[r]을 교환한다.
    i + 1을 반환한다.

처음에는 퀵_정렬(1, N)을 호출한다. \(p \ge r\)인 구간에서는 분할과 출력을 수행하지 않는다.

\(q\)는 기준 원소가 분할 후 놓인 위치이며, 다음 재귀 호출의 구간을 정할 때만 사용한다. \(q\) 자체는 출력하지 않는다.

\(A_j\)와 기준 원소의 값이 같으면 \(A_j\)를 왼쪽으로 옮기지 않는다.

입력

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

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

출력

분할이 끝날 때마다 다음 형식으로 한 줄에 출력한다.

p r : A[p] A[p + 1] ... A[r]

콜론의 앞과 뒤에는 각각 공백이 하나씩 있어야 한다.

제한 사항

• \(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 5 : 1 3 2 4 5
2 5 : 3 2 4 5
2 4 : 3 2 4
2 3 : 2 3

예제 설명 1

첫 번째 분할에서는 마지막 원소 \(1\)을 기준으로 사용한다. 분할이 끝나면 \(1\)은 첫 번째 위치에 놓인다. 왼쪽 구간에는 원소가 없으므로 오른쪽 구간 \([2,5]\)에 같은 과정을 반복한다.