Hôm nay cô giáo B dạy học sinh về dãy con tăng dài nhất. Dãy con tăng dài nhất là dãy con nhận được từ dãy ban đầu bằng cách xóa đi một số số, giữ nguyên thứ tự ban đầu, sao cho dãy còn lại thỏa mãn tính chất hai số cạnh nhau thì số đứng trước nhỏ hơn số đứng sau.

Sau khi dạy xong, cô giáo B thấy rằng một số số xuất hiện trong nhiều dãy con tăng dài nhất, cô gọi đó là số đặc biệt.

Yêu cầu

Cho dãy số nguyên \(a_1, a_2, ..., a_n\) khác nhau từng đôi một \((n \le 10^5, 1 \le a_i \le n)\). Số ai được gọi là một số đặc biệt đối với dãy số trên nếu như ai thuộc ít nhất một dãy con tăng dài nhất của A.

Tìm các số đặc biệt của dãy A.

Dữ liệu vào

• Dòng đầu ghi \(T (1 \le T \le 10)\) là số bộ test.
• T nhóm dòng tiếp theo, mỗi nhóm gồm hai dòng:
  • Dòng thứ nhất là số \(n\).
  • Dòng thứ hai là dãy số nguyên dương \(a_1, ..., a_n\).

Dữ liệu ra

• Gồm \(T\) dòng, mỗi dòng ghi các số đặc biệt của bộ test tương ứng theo giá trị tăng dần.

Input 1

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

Output 1

1 2 3 4 5 6
1 2 3 4 5

Ràng buộc

• Có 60% số test có \(n \le 10^2\).
• Có 40% số test còn lại có \(n \le 10^5\).