Dãy con tăng tham lam (Greedily Increasing Subsequence)

Nguồn: Kattis

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho một hoán vị $A=(a_1,\ldots,a_N)$ của các số $1,2,\ldots,N$. Xây dãy GIS như sau: lấy $g_1=a_1$; sau mỗi phần tử đã chọn, tiếp tục từ vị trí kế tiếp và lấy phần tử đầu tiên lớn hơn phần tử vừa chọn. Khi không còn phần tử như vậy thì dừng. Hãy in GIS.

Input

Dòng đầu chứa $N$. Dòng thứ hai chứa hoán vị $a_1,\ldots,a_N$.

Output

Dòng đầu in độ dài GIS. Dòng thứ hai in các phần tử GIS theo thứ tự.

Subtask

Các giới hạn chung:

• $1 \le N \le 2\cdot10^5$.

• $A$ là một hoán vị của $1,2,\ldots,N$.

• Subtask 1 (20 điểm): $N \le 20$

• Subtask 2 (30 điểm): $N \le 5000$

• Subtask 3 (50 điểm): Không có ràng buộc bổ sung.

Ví dụ

Input

7
2 3 1 5 4 7 6

Output

4
2 3 5 7

Giải thích

Bắt đầu ở $2$. Phần tử đầu tiên phía sau lớn hơn $2$ là $3$; tiếp theo là $5$; tiếp theo là $7$. Sau $7$ không còn số lớn hơn.