동전 게임

조 코더는 심심할 때 탁자 위의 동전으로 다음 게임을 즐긴다. 서로 값이 다른 동전 몇 개를 골라 한 줄로 늘어놓는다. 예를 들어 1센트짜리(P, $0.01), 5센트짜리(N, $0.05), 10센트짜리(D, $0.10)가 있다고 하자. 이들을 임의의 순서(예: D N P)로 늘어놓은 뒤, 값이 엄격히 증가하는 순서, 즉 P N D($0.01, $0.05, $0.10)가 되도록 옮긴다. 이때 다음 규칙을 지킨다.

• 처음 늘어놓은 배열이 동전을 놓을 수 있는 모든 자리를 정한다. 이후 자리를 새로 늘릴 수 없으며, 어떤 자리에 동전이 하나도 없더라도 그 자리는 그대로 존재한다.
• 게임은 여러 번의 이동으로 이루어진다. 한 번의 이동에서 조는 동전 하나를 지금 있는 자리에서 바로 옆 자리로 옮긴다.
• 동전은 쌓을 수 있다. 한 번의 이동에서 조는 언제나 한 무더기의 맨 위 동전을 집어 다른 무더기(또는 빈 자리)의 맨 위에 올린다.
• 한 무더기 안에서 조는 값이 더 큰 동전을 값이 더 작은 동전 위에 올리지 않는다.

편의상 동전에 연속한 정수 값을 매긴다(예: 1센트=1, 5센트=2, 10센트=3). 이 값으로 위 예시는 20번의 이동으로 풀 수 있다. 아래 표에서 XY는 동전 X가 동전 Y 위에 놓였다는 뜻이다.

어떤 시작 배열에서는 값이 엄격히 증가하는 목표에 도달하는 것이 불가능하다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 두 줄이다. 첫 줄에는 동전의 개수인 양의 정수 n(n < 5)이 주어지며, 동전에는 1, 2, 3, …, n의 번호가 붙어 있다. 둘째 줄에는 1부터 n까지의 수가 임의의 순서로 주어지는데, 이는 첫 번째 자리부터 마지막 자리까지의 처음 배열을 나타낸다.

숫자 0만 있는 줄이 나오면 입력이 끝난다.

각 테스트 케이스마다 한 줄을 출력한다. 조가 목표 배열에 도달할 수 있는 최소 이동 횟수를 출력하고, 도달할 수 없으면 IMPOSSIBLE을 출력한다.