비장의 카드

Amy는 값이 1부터 N까지인 N장의 카드로 이루어진 덱을 가지고 있다. Amy는 카드 값들에 길이가 3인 감소 부분 수열이 없도록 덱을 배열한다. 예를 들어, 1, 5, 4, 6, 3, 2은 올바르지 않은 순서인데, 5, 3, 2이 감소하기 때문이다.

이제 Amy는 카드 덱을 Ben에게 준다. Ben은 덱에 길이가 3인 감소 부분 수열이 없다는 사실은 알지만, 정확한 순서는 알지 못한다. 그는 값이 1인 카드를 찾고 싶어 한다. 이를 위해 임의의 카드 한 장을 골라 집어 들고 그 값을 확인하며, 값이 1인 카드를 찾을 때까지 이 과정을 반복한다. 각 단계에서 Ben은 자신이 확인해야 하는 카드 수의 최악의 경우를 최소화할 카드를 선택한다.

나중에 Ben은 운이 나빠서 값이 1인 카드를 찾기 전에 N장의 카드를 모두 확인해야 했다고 말한다. Ben이 덱의 카드를 확인한 순서가 주어질 때, 각 카드의 값은 무엇이었는가? 가능한 답이 여러 개라면 사전순으로 가장 큰 것을 선택한다.

덱 A이 덱 B보다 사전순으로 크다는 것은, 두 덱이 처음으로 달라지는 인덱스에서 A의 카드 값이 B의 카드 값보다 클 때, 그리고 그럴 때에만 성립한다.

예제: N = 3이고, Ben은 2, 1, 3 순서로 카드를 확인했다(인덱스는 1부터 시작한다). 카드의 값은 반드시 다음과 같았어야 한다: 2, 3, 1.

설명: 카드 #2의 값이 1이었다면 Ben은 즉시 멈췄을 것이다. 카드 #2의 값이 2이었다면 Ben은 첫 번째 카드가 반드시 1였어야 한다는 것을 알았을 것이다. 순서 (3, 2, 1)는 길이가 3인 감소 부분 수열이므로 카드의 순서일 수 없기 때문이다. 어느 경우든 Ben에게는 3번의 추측이 필요하지 않았을 것이다. 따라서 카드 #2의 값이 3였어야 한다고 추론할 수 있다. 마찬가지로 카드 #1의 값은 1일 수 없었다. 그렇다면 Ben이 일찍 멈출 수 있었기 때문이다. 따라서 카드의 값은 반드시 2, 3, 1였어야 한다.

제한

1 ≤ T ≤ 100 주어진 추측 순서에 대해, Ben의 전략상 N장의 카드를 확인해야 했다는 제약을 포함하여 문제의 모든 제약을 만족하는 덱이 적어도 하나 존재한다. 메모리 제한: 1GB.

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ N ≤ 8 시간 제한: 30초.

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ N ≤ 300 시간 제한: 60초.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 덱에 있는 카드의 수를 나타내는 하나의 정수 N이 담긴 줄로 시작한다. 다음 줄에는 Ben이 덱을 확인한 순서를 설명하는, 한 칸의 공백으로 구분된 N개의 정수가 주어진다. 첫 번째 정수는 그가 처음 확인한 카드의 1부터 시작하는 위치를 나타내고, 두 번째 정수는 그가 두 번째로 확인한 카드의 1부터 시작하는 위치를 나타내며, 이후도 같은 방식이다.

각 테스트 케이스마다 "Case #x: y"을 담은 한 줄을 출력한다. 여기서 x는 (1부터 시작하는) 케이스 번호이고, y는 공백으로 구분된 카드 값의 수열이다.