22243_SortthatQueue

Given a queue Q, a stack A, and a stack B, and the following operations:

QA(n): dequeue an item from Q, pushing it on A; repeat n times

QB(n): dequeue an item from Q, pushing it on B; repeat n times

QQ(n): dequeue an item from Q, enqueue it again in Q; repeat n times

AQ(n): pop an item from A, enqueue it in Q; repeat n times

BQ(n): pop an item from B, enqueue it in Q; repeat n times

AB(n): pop an item from A, push it on B; repeat n times

BA(n): pop an item from B, push it on A; repeat n times.

Note that each of the above is considered a single operation, regardless of the value of n.

Now assume that the queue is already populated with numbers and that both stacks are empty, what is the minimum number of operations needed to have the same numbers in the queue but sorted in an ascending order? (smallest in front.)

For example, the queue (4 3 1 2 0) where 4 is at the front, can be sorted in three steps as follows: QA(2), QQ(2), then AQ(2). The queue (5 4 1 3 2 0) can be sorted in four operations as follows: QB(2), QQ(1), QB(2), BQ(4).

Write a program that determines the minimum number of operations needed to sort a given queue.

Your program will be tested on a number of test cases. Each test case is specified on a single line. Each test case is made of N + 1 integers. The first integer specifies N which is the number of elements in the queue. A queue of N elements will have in it the integers from 0 to N - 1 in some random order. The integers in the queue are specified from the front of the queue to the back. No queue will have more than 10 elements.

The end of the test cases is identified with an input line that contains a single integer N = 0 (which is not part of the test cases.)

For each test case, write the result on a separate line.

5 4 3 1 2 0
6 5 4 1 3 2 0
0

3
4