Ancient Books timer 2초 memory 1024MB

테헤란에는 이란 국립 도서관이 있다.

이 도서관의 중요 보물이 개의 테이블이 일렬로 놓여진 긴 홀에 위치하는데, 이 테이블들은 왼쪽에서 오른쪽으로 0부터 n-1로 나타낸다.

각 테이블 위에는 한 권의 고대 책이 놓여있다.

이 책들은 처음에 연도별 순서로 놓여 있어서 방문객이 제목으로 책을 찾기에 어려움이 있었다.

그래서 도서관 관리자는 책 제목의 알파벳 순서로 책들을 정렬하기로 결정했다.

도서관 사서인 아리안이 이 일을 수행할 것이다.

그는 0부터 n-1까지의 서로 다른 정수들을 포함하는 길이 n의 리스트 p를 만든다.

이 리스트는 책들을 알파벳 순서로 정렬하는데 필요한 이동들을 나타낸다:

모든 0 ≤ i < n에 대해서, 현재 테이블 i에 놓여있는 책을 테이블 p_i로 옮겨야 한다.

아리안은 테이블 s에서 책 정렬을 시작한다.

그는 일을 끝낼 때 같은 테이블로 돌아올 것이다.

책들은 매우 귀중해서 어떤 순간에도 두 권 이상 운반할 수 없다.

책들을 정렬할 때, 아리안은 특정한 움직임들을 차례로 수행한다.

이 움직임은 다음 중 하나여야만 한다:

- 그가 책을 들고 있지 않고 그가 위치한 테이블에 책이 있다면, 그 책을 집어 들수 있다.

- 그가 책을 들고 있고 그가 위치한 테이블에 다른 책이 있다면, 들고 있는 책과 테이블 위의 책을 교환할 수 있다.

- 그가 책을 들고 있고 그가 빈 테이블 앞에 위치한다면, 들고 있는 책을 그 테이블에 놓을 수 있다.

- 그는 임의의 테이블로 이동할 수 있다. 이동 할 때, 한 권의 책을 들고 운반할 수 있다.

모든 0 ≤ i, j ≤ n-1에 대해서, 테이블 i와 j 사이의 거리는 정확히 |j-i| 이다.

당신이 할 일은 아리안이 모든 책들을 정렬하기 위해서 이동해야 하는 총 거리의 최소값을 계산하는 것이다​