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

병합 정렬은 배열의 구간을 절반씩 나눈 뒤, 나누어진 두 구간을 각각 정렬하고 하나의 정렬된 구간으로 합치는 정렬 알고리즘이다.

구간 \([l,r]\)의 중간 위치는 항상 \(m=\lfloor(l+r)/2\rfloor\)로 정한다. 왼쪽 구간 \([l,m]\)을 먼저 정렬한 뒤 오른쪽 구간 \([m+1,r]\)을 정렬한다.

의사 코드

정렬(l, r)
    if l >= r
        함수를 종료한다.

    m = (l + r) / 2의 몫

    정렬(l, m)
    정렬(m + 1, r)

    i = l
    j = m + 1
    빈 임시 배열 B를 만든다.

    while i <= m이고 j <= r인 동안
        if A[i] <= A[j]
            B의 뒤에 A[i]를 넣는다.
            i = i + 1
        else
            B의 뒤에 A[j]를 넣는다.
            j = j + 1

    while i <= m인 동안
        B의 뒤에 A[i]를 넣는다.
        i = i + 1

    while j <= r인 동안
        B의 뒤에 A[j]를 넣는다.
        j = j + 1

    B의 원소를 순서대로 A[l]부터 A[r]까지 복사한다.
    l, r, 콜론(:), A[l]부터 A[r]까지의 원소를 출력한다.

처음에는 정렬(1, N)을 호출한다. 원소가 하나인 구간은 출력하지 않으며, 두 구간의 병합이 끝난 직후에만 출력한다.

두 값이 같으면 왼쪽 구간에 있는 값을 먼저 임시 배열에 넣는다.

입력

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

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

출력

두 구간을 병합할 때마다 다음 형식으로 한 줄에 출력한다.

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

콜론의 앞과 뒤에는 각각 공백이 하나씩 있어야 한다. 총 \(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 2 : 3 5
1 3 : 2 3 5
4 5 : 1 4
1 5 : 1 2 3 4 5

예제 설명 1

구간 \([1,5]\)는 \([1,3]\)과 \([4,5]\)로 나뉜다. 왼쪽 구간을 먼저 처리하므로 \([1,2]\), \([1,3]\), \([4,5]\), \([1,5]\)의 순서로 병합 결과가 출력된다.