저글러

한 손으로 여러 개의 공을 원형으로 돌리며 저글링을 하고 있습니다. 공연을 마무리하기 위해, 정해진 순서대로 모든 공을 최소한의 이동 횟수로 떨어뜨리려고 합니다.

한 번의 이동에서 다음 중 정확히 하나를 할 수 있습니다.

• 모든 공을 반시계 방향으로 한 칸 회전한다,
• 모든 공을 시계 방향으로 한 칸 회전한다,
• 지금 손에 있는 공을 떨어뜨린다.

손에 있는 공을 떨어뜨리면, 시계 방향으로 바로 다음 공이 즉시 손에 들어옵니다.

공을 떨어뜨려야 하는 순서가 주어질 때, 모든 공을 떨어뜨리는 데 필요한 최소 이동 횟수를 구하세요.

입력은 여러 개의 테스트 케이스로 이루어져 있습니다. 각 테스트 케이스의 첫 줄에는 저글링하는 공의 개수를 나타내는 정수 $n$ ($1 \le n \le 100{,}000$)이 주어집니다.

이어지는 $n$개의 줄에는 각각 하나의 정수 $k_i$ ($1 \le k_i \le n$)가 주어집니다. 여기서 $i$는 손에 있는 공(위치 $1$)에서부터 시계 방향으로 센 공의 위치이고, $k_i$는 그 공을 떨어뜨려야 하는 순서입니다. 값 $k_1, k_2, \ldots, k_n$은 $1$부터 $n$까지의 순열입니다.

입력의 마지막 줄에는 $0$ 하나가 주어지며, 이 줄은 어떤 테스트 케이스에도 포함되지 않습니다.

각 테스트 케이스마다, 정해진 순서대로 모든 공을 떨어뜨리는 데 필요한 최소 이동 횟수를 한 줄에 하나의 정수로 출력하세요.

불필요한 공백을 출력하지 말고, 답 사이에 빈 줄을 넣지 마세요. 모든 답은 부호 있는 64비트 정수 범위에 들어갑니다.

공이 세 개인 예시를 생각해 봅시다. 손에 있는 공은 세 번째로, 시계 방향으로 바로 다음 공은 두 번째로, 그 다음 공은 첫 번째로 떨어뜨려야 합니다.

한 칸 회전하여 가장 먼저 떨어뜨려야 하는 공을 손으로 가져와 떨어뜨리면, 그 공의 시계 방향 이웃이 즉시 손에 들어옵니다. 한 번 더 회전하고 두 번 더 떨어뜨리면 공연이 끝나며, 총 다섯 번의 이동이 필요합니다.