SP7851 JZPSTA - Stacks of Zippy

Recently [Zippy](../JZPCIR/) recieved four stacks, named A B C D respectively. Firstly, there are n elements in stack A (the element sequence is a permutation of 1..n), and stack B C D are empty. He can do four types of operations: operation a: push the top element of stack A to stack B (if stack A is not empty, this operation can be done) operation b: push the top element of stack B to stack D (if stack B is not empty, this operation can be done) operation c: push the top element of stack A to stack C (if stack A is not empty, this operation can be done) operation d: push the top element of stack C to stack D (if stack C is not empty, this operation can be done) He can do 2\*n operations in total. Obviously, there are n elements in stack D after he did the 2\*n operations. Then he take out the top element in stack D one by one. If the first element he takes out is n, the second is n-1, ... , the last is 1, he will be very happy. Also, he wants to make the operation sequence he did lexicographic smallest. Input

First line is a number t, which is the number of testcases. Then following t testcases. For each test case, the first line contains a number n, which denotes the number of the elements in stack A. The second line contains n numbers, separated by a space, which are the elements in stack A, from top to the bottom. You can be sure that the sum of all n does not exceed 200000, and each n is not bigger than 100000.

N/A