[HSG_BN_24] Số đặc biệt

Xem dạng PDF
Gửi bài giải
Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Pascal, Python

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 xoá đi một số số, giữ nguyên thứ tự ban đầu, sao cho dãy còn lại thoả 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.

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ố ~a_i~ được gọi là một số đặc biệt đối với dãy số trên nếu như ~a_i~ thuộc ít nhất một dãy con tăng dài nhất của ~A~.

Yêu cầu

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

Dữ liệu đầu vào

Gồm ~2 \times T + 1~ dòng:

  • 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à ~n~ số nguyên có thứ tự từ ~1~ đến ~n~.

Dữ liệu đầ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.

Ràng buộc dữ liệu

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

Ví dụ

Ví dụ 1
INPUT
2
7
1 2 3 7 4 5 6
5
1 4 3 2 5
OUTPUT
1 2 3 4 5 6
1 2 3 4 5

Bình luận

Hãy đọc nội quy trước khi bình luận.