밧줄 우편

우리는 다양한 통신 수단에 익숙하다. 전화, 전자 우편, 소셜 네트워크는 지구 반대편에 있는 사람에게도 정보를 전달할 수 있게 해 준다. 전자 우편과 메신저 서비스를 제공하는 어느 유명 회사는 입사 지원자에게 "밧줄 우편"이라는 시스템으로 모든 메시지를 수신자에게 전달하는 최소 시간을 계산하는 과제를 낸다.

시스템은 다음과 같다. 밧줄이 팽팽하게 놓인 하나의 직선 위에 1번부터 n번까지 차례로 번호가 붙은 n명의 사람이 있다. 번호가 1만큼 차이나는 사람 사이에는 아무도 없고, 이런 모든 이웃 사이의 거리는 1미터로 같다.

각 사람은 다른 참가자 한 명에게 메시지를 보내려 한다. 즉 i번 사람은 ai번 사람에게 메시지를 보내려 한다. 각 사람은 자신의 메시지가 든 봉투를 자기 근처의 밧줄에 고정하고 봉투에 수신자 번호를 적는다. 그다음 밧줄이 직선을 따라 여러 번, 여러 방향으로 움직이고, 자신에게 온 봉투가 자기 앞에 나타나면 그 사람은 봉투를 가져가 메시지를 받는다.

밧줄은 일정한 속도로 움직이므로 모든 메시지가 수신자에게 도달하는 시간은 밧줄이 움직인 총 거리에 달려 있다. 면접 지원자에게 주어지는 과제는 이 거리를 최소화하는 것이다.

예를 들어 첫 번째 사람이 두 번째 사람에게, 두 번째 사람이 세 번째 사람에게, 세 번째 사람이 두 번째 사람에게, 네 번째 사람이 첫 번째 사람에게 메시지를 보내려 한다고 하자. 그러면 밧줄을 앞으로 1미터 움직여야 하고, 그러면 두 번째 사람이 첫 번째 사람의 메시지를, 세 번째 사람이 두 번째 사람의 메시지를 받는다. 그다음 밧줄을 뒤로 2미터 움직이고(그러면 두 번째 사람이 세 번째 사람의 메시지를 받는다), 다시 2미터 움직인다(첫 번째 사람이 네 번째 사람의 메시지를 받는다). 따라서 밧줄을 모두 5미터 움직여야 한다.

첫째 줄에는 메시지를 주고받는 사람 수 n이 정수로 주어진다 (2 ≤ n ≤ 1000). 둘째 줄에는 n개의 정수 ai가 주어진다 (1 ≤ ai ≤ n, ai ≠ i). ai는 i번 참가자의 메시지가 향하는 사람의 번호이다.

모든 메시지가 제 주소로 도착하도록 밧줄을 움직여야 하는 최소 총 거리를 정수 하나로 출력한다.