숨겨진 에이스 (스몰)

에이미는 $1$부터 $N$까지의 값이 하나씩 적힌 카드 $N$장으로 덱을 만든다. 값의 나열에 길이 $3$인 감소 부분수열이 생기지 않도록 배치한다. 예를 들어 $1, 5, 4, 6, 3, 2$는 $5, 3, 2$가 감소하므로 허용되지 않는다.

에이미는 이 덱을 벤에게 넘긴다. 벤은 덱에 길이 $3$인 감소 부분수열이 없다는 사실은 알지만 정확한 배치는 모른다. 벤은 값이 $1$인 카드를 찾으려 한다. 카드를 하나 골라 뒤집어 값을 확인하고, 값 $1$을 찾을 때까지 이 과정을 반복한다. 매 단계에서 벤은 앞으로 확인해야 하는 카드 수의 최악값이 가장 작아지는 카드를 고른다.

나중에 벤은 운이 나빠서 값 $1$을 찾기까지 카드 $N$장을 모두 확인했다고 말한다. 벤이 카드를 확인한 순서가 주어질 때 각 카드의 값을 구하라. 가능한 덱이 여럿이면 사전순으로 가장 큰 덱을 고른다.

덱 $A$가 덱 $B$보다 사전순으로 크다는 것은, 두 덱이 처음으로 달라지는 위치에서 $A$의 카드 값이 더 크다는 뜻이다.

$N = 3$이고 벤이 확인한 위치가 순서대로 $2, 1, 3$인 경우를 보자(위치는 $1$부터 센다). 카드 값은 $2, 3, 1$이어야 한다. $2$번 카드의 값이 $1$이었다면 벤은 곧바로 멈췄을 것이다. $2$번 카드의 값이 $2$였다면, 배치가 $(3, 2, 1)$일 때 길이 $3$인 감소 부분수열이 되어 불가능하므로 벤은 $1$번 카드가 값 $1$임을 알아냈을 것이다. 두 경우 모두 세 번째 확인은 필요하지 않다. 따라서 $2$번 카드의 값은 $3$이다. 같은 이유로 $1$번 카드의 값도 $1$일 수 없다. 그러므로 카드 값은 $2, 3, 1$이다.

첫 줄에 테스트 케이스 수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 덱의 카드 수 $N$이 주어진다. 다음 줄에는 벤이 카드를 확인한 순서를 나타내는 정수 $N$개가 공백 하나로 구분되어 주어진다. $i$번째 정수는 벤이 $i$번째로 확인한 카드의 위치이며, 위치는 $1$부터 센다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 $1$부터 시작하는 테스트 케이스 번호이고, $y$는 카드 값을 위치 순서대로 공백 하나로 구분해 나열한 것이다.

• $1 \le T \le 100$
• $1 \le N \le 8$
• 주어진 확인 순서에 대해, 벤이 카드 $N$장을 모두 확인해야 한다는 조건까지 포함해 문제의 모든 조건을 만족하는 덱이 적어도 하나 존재한다.