암호조작 timer 1초 memory 256MB

서현이는 자기가 만든 비밀 최종병기 알고리즘의 사용방법을 컴퓨터에 저장해놓고, x₁,x₂,...x_<n의 n개의 정수 수열로 이루어진 암호를 걸어놓았다.

서현이는 이 비밀 알고리즘을 이용하여 다음 온라인 콘테스트에서 고득점을 받을 계획이다.

x₁부터 x_n까지의 정수들은 1부터 n까지의 정수 중 하나이며, 수열 내의 어떤 두 수도 같은 값을 가지지 않는다. (즉, 이 수열은 쉽게 말하면, 1부터 n까지의 숫자로 만든 순열 중 하나이다.)

"이 최종병기 알고리즘의 사용방법을 참고하려면, 암호를 맞추는 수밖에 없는데, 총 n!개의 경우의 수가 있으므로, 다른 사람이 이 알고리즘 사용법을 열람하는 것은 사실상 불가능하다." ...라고 서현이는 착각하며 순수한 표정으로 미소를 지으며 잠자리에 들었다...

민기는 서현이에게 비밀 최종병기 알고리즘이 있다는 사실을 알아채고, 서현이가 콘테스트 당일날 이 알고리즘을 사용하지 못 하게 하려고 한다.

해킹 툴을 이용하여 암호 수열쯤은 간단하게 알아버린 영악한 민기는 아예 설명서 파일을 삭제해 버려도 되겠지만, 한 술 더 떠서, 서현이가 알아채지 못하게 서현이의 암호를 자기만의 규칙으로 조작해버리려고 한다. 그렇게 하면 최종병기 알고리즘을 서현이는 못 쓰고, 대신 본인만이 쓸 수 있기 때문이다.

민기는 바이러스를 이용하여 몰래 암호 수열을 조작할 것인데, 조작 규칙은 다음과 같다.

- k = 2, 3, 4, ... n까지 오름차순 순서대로 k값을 순회하면서,

- x_k와 x_k/2​의 값을 맞바꾸거나 (k가 홀수인 경우, k/2는 정수부분만을 의미.)

- 그대로 둔다.

이러한 조작 방식은 각 k값에 대하여 두 가지 선택지가 있기 때문에, 조작 후에 나올 수 있는 수열은 너무나도 많다.

그러면 민기 본인도 조작 후의 암호 수열을 모르기 때문에, 이 규칙만으로는 의미가 없다.

따라서 민기는 자신의 바이러스에 다음과 같은 규칙을 추가하려고 한다.

- 위 규칙을 적용하여 결과로써 나올 수 있는 모든 수열 중, 

  가장 사전순으로 빠른 수열을 최종 조작된 수열의 결과물로 한다.

그러나 민기는 바이러스만 잘 만들지, 알고리즘 시간에는 여러분들처럼 버그투성이 코드만 쓰다 보니 이 마지막 규칙을 적용하는 것이 조금 버거운 것 같다.

아무래도, 여러분이 민기와 힘을 합쳐 이 프로그램을 완성해야 할 것 같다.

민기를 도와 프로그램의 핵심 부분인 수열 조작 부분을 완성하여 공범으로써 서현이의 최종 병기 알고리즘에 대한 지분을 받아내보자.

 ※ 사전순: 수열[a₁ , a₂ , ... a_n]과  [b₁, b₂, ... , b_n]을 비교했을 때, 어떤 정수 i에 대하여 j<i인 모든 j에 대하여 a_j = b_j이고, a_i<b_i를 만족한다면, 왼쪽 수열이 오른쪽 수열보다 사전순으로 빠르다고 한다.