Ace in the Hole

Amy has a deck of $N$ cards whose values are 1 through $N$, one value per card. She lays the cards in a row so that the sequence of values has no decreasing subsequence of length 3. For example, 1, 5, 4, 6, 3, 2 breaks the rule, because 5, 3, 2 is decreasing.

Amy gives the deck to Ben. Ben knows the deck has no decreasing subsequence of length 3, but he does not know the exact arrangement. He wants to find the card with value 1. He picks one card, looks at its value, and repeats until he finds the card with value 1. At each step Ben considers every arrangement that agrees with the values he has already seen, then picks a card that minimizes the worst-case number of cards he still has to examine.

Ben says he was unlucky and examined all $N$ cards before he found the card with value 1. Given the order in which he examined the cards, find the value of each card. If several arrangements are possible, choose the lexicographically greatest one.

A deck $A$ is lexicographically greater than a deck $B$ when, at the first position where the two differ, the value in $A$ is greater than the value in $B$.

The first line contains the number of test cases $T$. Each test case begins with a line containing one integer $N$, the number of cards in the deck. The next line contains $N$ integers separated by single spaces, describing the order in which Ben examined the deck. The $i$-th integer is the position of the card he examined $i$-th, and positions are counted from 1.

For each test case, print one line in the form "Case #x: y", where $x$ is the test case number starting from 1 and $y$ is the values of the cards from the first to the $N$-th, separated by single spaces.

• $1 \le T \le 100$
• $1 \le N \le 300$
• The examination order is a permutation in which each position from 1 to $N$ appears exactly once.
• For the given examination order, at least one deck meets every condition of the problem, including the condition that Ben had to examine all $N$ cards.