큐 소트

큐 $Q$와 두 개의 스택 $A$, $B$가 있고, 다음 7가지 연산을 사용할 수 있다.

• QA(n): $Q$에서 수를 하나 꺼내 $A$에 넣는다. 이 동작을 $n$번 반복한다.
• QB(n): $Q$에서 수를 하나 꺼내 $B$에 넣는다. 이 동작을 $n$번 반복한다.
• QQ(n): $Q$에서 수를 하나 꺼내 다시 $Q$에 넣는다. 이 동작을 $n$번 반복한다.
• AQ(n): $A$에서 수를 하나 꺼내 $Q$에 넣는다. 이 동작을 $n$번 반복한다.
• BQ(n): $B$에서 수를 하나 꺼내 $Q$에 넣는다. 이 동작을 $n$번 반복한다.
• AB(n): $A$에서 수를 하나 꺼내 $B$에 넣는다. 이 동작을 $n$번 반복한다.
• BA(n): $B$에서 수를 하나 꺼내 $A$에 넣는다. 이 동작을 $n$번 반복한다.

$Q$는 큐(FIFO)이므로 수를 꺼낼 때는 항상 맨 앞에서 꺼내고 넣을 때는 항상 맨 뒤에 넣는다. $A$와 $B$는 스택(LIFO)이므로 꺼낼 때는 항상 맨 위에서 꺼내고 넣을 때는 맨 위에 쌓는다.

각 연산은 $n$의 값과 관계없이 한 번으로 센다.

처음에 큐에는 수가 모두 채워져 있고 두 스택은 비어 있다. 큐에 들어 있는 수를 맨 앞에서 맨 뒤로 읽었을 때 오름차순이 되도록 만들려고 한다. 이때 필요한 연산 횟수의 최솟값을 구하여라. (정렬이 끝난 상태에서는 모든 수가 다시 큐 안에 있어야 하고 두 스택은 비어 있어야 한다.)

예를 들어 큐가 (4 3 1 2 0)이면 QA(2), QQ(2), AQ(2)의 순서로 3번 만에 정렬할 수 있고, 큐가 (5 4 1 3 2 0)이면 QB(2), QQ(1), QB(2), BQ(4)의 순서로 4번 만에 정렬할 수 있다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 한 줄로 주어지며, 그 줄의 첫 번째 정수는 큐에 들어 있는 수의 개수 $N$이다. 이어서 큐의 맨 앞에서부터 순서대로 $N$개의 수가 주어진다.

큐에 들어 있는 수는 모두 $0$ 이상 $N-1$ 이하의 정수이고, 각 수는 정확히 한 번씩만 나타난다. $N$은 $10$을 넘지 않는다.

입력의 마지막 줄에는 $0$이 하나 주어지며, 이 줄은 처리하지 않고 입력의 끝을 뜻한다.

각 테스트 케이스마다 큐를 오름차순으로 정렬하는 데 필요한 연산 횟수의 최솟값을 한 줄에 하나씩 출력한다.