Ace in the Hole (Small)

Amy builds a deck of $N$ cards, each carrying one value from $1$ to $N$. She arranges the deck so that the values contain no decreasing subsequence of length $3$. For example, $1, 5, 4, 6, 3, 2$ is not allowed because $5, 3, 2$ decreases.

Amy hands the deck to Ben. Ben knows the deck has no decreasing subsequence of length $3$, but he does not know the arrangement. Ben wants to find the card with value $1$. He picks a card, turns it over to read its value, and repeats until he finds value $1$. At every step Ben picks a card that minimizes the worst-case number of cards he still has to examine.

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

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

Take $N = 3$ with Ben examining positions in the order $2, 1, 3$, where positions are counted from $1$. The values must have been $2, 3, 1$. If card $2$ held value $1$, Ben would have stopped at once. If card $2$ held value $2$, Ben would have known that card $1$ holds value $1$, because the arrangement $(3, 2, 1)$ contains a decreasing subsequence of length $3$ and is impossible. Neither case needs a third examination. Card $2$ therefore held value $3$. For the same reason card $1$ did not hold value $1$. The values are $2, 3, 1$.

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 Ben examined $i$-th, with positions 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 in position order, separated by single spaces.

• $1 \le T \le 100$
• $1 \le N \le 8$
• For the given examination order, at least one deck satisfies every condition in the problem, including the condition that Ben had to examine all $N$ cards.