엘리베이터 조작
시간 제한1초메모리 제한512 MB
각 층에 한 명씩 있고 각자의 목적지 층이 주어진다. 1층에서 출발하는 1인용 엘리베이터로 모든 사람을 목적지에 내려주는 최소 버튼 횟수와 그 순서를 구한다.
문제
의찬이는 '아주 소프트웨어' 본사 건물의 관리자이다. 평소처럼 지루한 업무를 보던 어느 날, 아주 소프트웨어 본사의 엘리베이터가 고장 났다. 회사 사람들에게 엘리베이터를 고치는 데 하루가 걸린다고 알리자 사람들이 불평을 쏟아 내기 시작했다. 의찬이는 어쩔 수 없이 관리실에서만 조작할 수 있는 비상용 엘리베이터를 쓰기로 했다.
비상용 엘리베이터에는 최대 한 명만 탑승할 수 있고, 관리실에서만 조작할 수 있다. 관리실에는 엘리베이터를 움직이는 버튼들이 있어서, 관리실에서 원하는 층의 버튼을 누르면 엘리베이터가 그 층으로 이동한다.
의찬이는 매일 관리실에서 CCTV를 보며 회사 사람들의 이동 패턴을 지겹도록 지켜봤기 때문에, CCTV로 엘리베이터 앞에 기다리는 사람이 누구인지 보기만 해도 그 사람이 어느 층으로 가려는지 알 수 있다. 의찬이는 CCTV로 기다리는 사람이 누구인지 확인한 뒤, 최소한의 조작으로 엘리베이터를 움직여 각자 원하는 층에서 내려주려고 한다.
각 층에 사람이 한 명씩 기다리고 있다. 모든 사람을 원하는 층에서 내려주기 위해 눌러야 하는 버튼 횟수의 최솟값과 눌러야 하는 버튼 순서를 출력한다. 엘리베이터는 처음에 1층에 있다.
<그림 1> 예시 1
입력
첫째 줄에 건물의 층 수 N이 주어진다. (2 ≤ N ≤ 100,000)
다음 줄에 N개의 정수 A1, ..., AN이 주어지는데, Ai는 i층에서 기다리는 사람이 가려는 층이다. (1 ≤ Ai ≤ N, 1 ≤ i ≤ N)
현재 층으로 이동하려는 경우는 없다. (Ai ≠ i)
출력
첫째 줄에 눌러야 하는 버튼 횟수의 최솟값을 출력한다.
다음 줄에 눌러야 하는 버튼 순서를 공백으로 구분해 출력한다. 가능한 방법이 여러 가지라면 그중 아무거나 하나를 출력한다.
힌트
예제 1의 경우, 1층에서 사람을 태워 4층으로 이동해 내려주고, 4층에서 사람을 태워 5층으로 이동해 내려주고, 5층에서 사람을 태워 2층으로 이동해 내려주고, 2층에서 사람을 태워 4층으로 이동해 내려주고, 3층으로 이동해 3층에서 사람을 태워 1층으로 이동해 내려주면 된다.