레이팅 미적용\(A_{1}\), \(A_{2}\), …, \(A_{N}\)으로 표시된 N 개의 카드를 정해진 방법으로 섞고자 한다. 그 섞는 방법은 1에서 N까지의 숫자로 이루어진 수열로 표시된다. 이 수열을 섞기 수열이라 하자. 섞기는 현재 가지고 있는 카드에서 섞기 수열의 각 숫자가 나타내는 위치에 있는 카드를 순서대로 뽑아서 나열하는 것이다. 예를 들어, \(N = 6\)이고 섞기 수열이 [3, 2, 5, 6, 1, 4]라고 하자. 카드의 처음 상태가 [\(A_{1}\), \(A_{2}\), \(A_{3}\), \(A_{4}\), \(A_{5}\), \(A_{6}\)]일 때, 섞기를 한 번 실행하면 카드의 순서가 다음과 같이 된다.
[\(A_{3}\), \(A_{2}\), \(A_{5}\), \(A_{6}\), \(A_{1}\), \(A_{4}\)]
이 상태에서 다시 한 번 섞기를 실행하면 카드의 순서가 [\(A_{5}\), \(A_{2}\), \(A_{1}\), \(A_{4}\), \(A_{3}\), \(A_{6}\)]이 되고, 다시 한 번 더 섞기를 실행하면 카드의 순서가 [\(A_{1}\), \(A_{2}\), \(A_{3}\), \(A_{6}\), \(A_{5}\), \(A_{4}\)]가 된다. 이렇게 섞기를 반복하면 카드의 순서가 처음 상태인 [\(A_{1}\), \(A_{2}\), \(A_{3}\), \(A_{4}\), \(A_{5}\), \(A_{6}\)]이 된다. 처음 상태로 돌아 올 때까지 반복한 섞기의 최소 횟수를 주어진 섞기 수열의 궤적이라 한다. 임의의 섞기 수열이 주어졌을 때, 그 섞기 수열의 궤적을 구하는 프로그램을 작성하시오.
※ 이 문제의 채점 데이터는 공개된 공식 데이터가 없어 재구성한 것입니다. 문제 지문은 원본(정보올림피아드 기출)을 따릅니다.
첫 번째 줄에 카드의 수 N이 주어진다. N은 1 이상 20,000 이하의 수이다. 두 번째 줄에 섞기 수열을 나타내는 N 개의 자연수가 빈칸을 사이에 두고 주어진다.
첫 번째 줄에 입력으로 주어진 섞기 수열의 궤적을 출력한다. 단, 궤적이 1 이상 2,000,000,000 이하인 입력만 주어진다.
6
3 2 5 6 1 4
6
생성자가 기록되지 않았습니다.
출처 올림피아드 > 한국정보올림피아드 > KOI 2009 > 2차 대회 > 고등부 1번