Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language
version or invalid test data, or description of the problem is not clear.
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.
Input
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.)
Output
For each test case, write the result on a separate line.
Example
Input:
5 4 3 1 2 0
6 5 4 1 3 2 0
0
Output
3
4
RSS