Amy có một bộ bài gồm \(N\) lá bài có giá trị từ \(1\) đến \(N\). Cô ấy sắp xếp bộ bài sao cho các giá trị của các lá bài không có dãy con giảm dần độ dài 3. Ví dụ, \(1, 5, 4, 6, 3, 2\) là một thứ tự không hợp lệ vì \(5, 3, 2\) là một dãy con giảm dần.

Bây giờ Amy đưa bộ bài cho Ben. Ben biết rằng bộ bài không có dãy con giảm dần độ dài 3, nhưng anh ấy không biết thứ tự chính xác. Anh ấy muốn tìm lá bài có giá trị 1. Anh ấy thực hiện việc này bằng cách chọn một lá bài bất kỳ, lật nó lên để xem giá trị, và lặp lại cho đến khi tìm thấy lá bài có giá trị 1. Ở mỗi bước, Ben chọn một lá bài sao cho số lượng lá bài anh ấy phải kiểm tra trong trường hợp xấu nhất là tối thiểu.

Sau đó, Ben nói với bạn rằng anh ấy đã không may mắn và phải kiểm tra tất cả \(N\) lá bài mới tìm thấy lá bài có giá trị 1. Cho biết thứ tự các vị trí mà Ben đã kiểm tra, hãy xác định giá trị của mỗi lá bài trong bộ bài là bao nhiêu? Nếu có nhiều khả năng, hãy chọn bộ bài có thứ tự từ điển lớn nhất.

Một bộ bài A được gọi là lớn hơn về mặt từ điển so với bộ bài B nếu và chỉ nếu, tại vị trí đầu tiên mà chúng khác nhau, lá bài trong A có giá trị lớn hơn giá trị của lá bài trong B.

Ví dụ: \(N = 3\), và Ben đã thử các lá bài theo thứ tự vị trí là \(2, 1, 3\) (các vị trí được đánh số từ 1). Giá trị của các lá bài phải là: \(2, 3, 1\).

Giải thích: Nếu lá bài thứ #2 có giá trị 1, Ben sẽ dừng lại ngay lập tức. Nếu lá bài thứ #2 có giá trị 2, Ben sẽ biết lá bài đầu tiên phải là 1, vì thứ tự \((3, 2, 1)\) chứa dãy con giảm dần độ dài 3, nên không thể xảy ra. Trong cả hai trường hợp, Ben sẽ không cần đến 3 lần đoán. Do đó, ta có thể suy ra lá bài thứ #2 phải có giá trị 3. Tương tự, lá bài thứ #1 không thể có giá trị 1, nếu không Ben đã dừng lại sớm hơn. Vì vậy, các giá trị lá bài phải là \(2, 3, 1\).

Dữ liệu vào

Dòng đầu tiên của đầu vào cho biết số lượng bộ test, \(T\). Tiếp theo là \(T\) bộ test. Mỗi bộ test bắt đầu bằng một dòng chứa một số nguyên \(N\), số lượng lá bài trong bộ bài. Dòng tiếp theo chứa \(N\) số nguyên cách nhau bởi dấu cách, mô tả thứ tự các vị trí mà Ben đã kiểm tra: số nguyên đầu tiên là vị trí (đánh số từ 1) của lá bài đầu tiên anh ấy kiểm tra, số nguyên thứ hai là vị trí của lá bài thứ hai, và cứ tiếp tục như vậy.

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là dãy giá trị của các lá bài theo đúng thứ tự vị trí từ 1 đến \(N\), cách nhau bởi dấu cách.

Ràng buộc

• \(1 \le T \le 100\)
• Đối với dãy các lần đoán được cung cấp, chắc chắn có ít nhất một bộ bài thỏa mãn tất cả các ràng buộc của bài toán, bao gồm cả ràng buộc rằng chiến thuật của Ben yêu cầu anh ấy phải xem tất cả \(N\) lá bài.

Phân nhóm

• Test set 1 (Visible): \(1 \le N \le 8\).
• Test set 2 (Hidden): \(1 \le N \le 300\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

3
3
2 1 3
1
1
3
3 2 1

Case #1: 2 3 1
Case #2: 1
Case #3: 1 3 2

Nguồn

Google Code Jam 2011, Chung kết thế giới, bài Ace in the Hole.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.