Farmer John có \(N\) (\(1\leq N\leq 2\cdot 10^5\)) con bò trong một hàng \(a\). Con bò thứ \(i\) tính từ đầu hàng \(a\) được gắn nhãn là số nguyên \(a_i\) (\(1\leq a_i\leq N\)). Nhiều con bò có thể mang cùng một nhãn.

FJ sẽ tạo một hàng khác \(b\) theo cách sau:

• Ban đầu, \(b\) rỗng.
• Trong khi \(a\) chưa rỗng, lấy con bò ở đầu hàng \(a\) ra và có thể thêm con bò đó vào cuối hàng \(b\).

FJ muốn tạo hàng \(b\) sao cho dãy nhãn trong \(b\) từ đầu đến cuối là lớn nhất theo thứ tự từ điển (xem ghi chú).

Trước khi tạo hàng \(b\), ông có thể thực hiện thao tác sau nhiều nhất một lần:

• Chọn một con bò trong hàng \(a\) và chuyển nó đến bất kỳ vị trí nào nằm trước vị trí hiện tại của nó.

Giả sử FJ thực hiện tối ưu thao tác nói trên nhiều nhất một lần, hãy in ra dãy nhãn lớn nhất theo thứ tự từ điển của \(b\) mà ông có thể đạt được.

Mỗi dữ liệu vào gồm \(T\) (\(1\leq T\leq 100\)) trường hợp kiểm thử độc lập.

Dữ liệu vào

Dòng đầu tiên chứa \(T\).

Dòng đầu tiên của mỗi trường hợp kiểm thử chứa \(N\).

Dòng thứ hai của mỗi trường hợp kiểm thử chứa \(N\) số nguyên cách nhau bởi dấu cách \(a_1,a_2,\ldots,a_N\).

Đảm bảo tổng \(N\) trên tất cả các trường hợp kiểm thử không vượt quá \(10^6\).

Dữ liệu ra

Với mỗi trường hợp kiểm thử, in hàng \(b\) lớn nhất theo thứ tự từ điển trên một dòng mới.

Ví dụ

3
5
4 3 2 1 3
6
5 1 2 6 3 4
6
4 1 3 2 1 1

4 3 3 2 1
6 5 4
4 3 2 1 1

Phân nhóm

• Dữ liệu 2–4: \(N\leq 100\).
• Dữ liệu 5–8: \(N\leq 750\).
• Dữ liệu 9–18: Không có ràng buộc bổ sung.

Ghi chú

Nhắc lại rằng một dãy \(s\) lớn hơn một dãy \(t\) theo thứ tự từ điển khi và chỉ khi một trong các điều sau đúng:

• Tại vị trí đầu tiên \(i\) mà \(s_i\neq t_i\), ta có \(s_i>t_i\).
• Nếu không tồn tại \(i\) như vậy, \(s\) dài hơn \(t\).

Nguồn

USACO 2025 February Contest, Silver — The Best Lineup. Tác giả: Chongtian Ma, Haokai Ma, Andrew Li.

https://usaco.org/index.php?page=viewproblem2&cpid=1494