블랙 박스

아래는 양의 정수들이 담긴 리스트를 받아 특정한 방식으로 섞은 뒤 결과를 리스트로 돌려주는 함수 BlackBox()의 Python 유사 의사코드이다.

아래에서 리스트 메서드 세 가지를 사용한다. 리스트 L에 대해 len(L)은 L의 원소 개수를 돌려준다. L.append(x)는 원소 x를 L의 끝에 추가한다. L.pop(idx)는 L에서 인덱스 idx의 원소를 제거하고, 제거한 원소를 돌려준다.

function BlackBox( Banana ):
    if len( Banana ) ≤ 4 :
        exit("Too small Banana")
    Apple = [] # [] is an empty list
    Mango = 0
    Papaya = len( Banana )

    while( Papaya >= 2 ) :
        Kiwi = Banana[ Mango ]
        Apple.append( Kiwi )
        Banana.pop( Mango )
        Papaya = Papaya - 1
        Mango = ( Kiwi + Mango - 1 ) % Papaya
    # end of while

    Apple.append( Banana[ 0 ] )
    Pear = len( Apple ) - 1
    Orange = Apple[ Pear ]
    Lime = Apple[ 0 ]
    Coconut = Orange % Pear
    Melon = Apple[ Coconut ]
    Apple[ 0 ] = Melon
    Apple[ Coconut ] = Lime

    return ( Apple )
# end of function BlackBox

양의 정수로 이루어진 리스트 Z가 주어진다. Z = BlackBox(I)를 만족하는 리스트 I를 복원하는 프로그램을 작성하라.

첫째 줄에 리스트 Z에 담긴 정수의 개수인 양의 정수 $n$이 주어진다. 여기서 $5 \le n \le 200\,000$이다. 이어지는 $n$개의 줄에는 Z의 정수가 한 줄에 하나씩 주어진다. $i$번째 줄에는 Z의 $i$번째 정수가 있으며, 이 값은 $1$ 이상 $100\,000$ 이하이다.

Z = BlackBox(I)를 만족하는 리스트 I의 정수 $n$개를 한 줄에 하나씩 출력한다. $i$번째 줄에는 I의 $i$번째 정수를 출력한다.