Cho dãy số nguyên ~A~ gồm ~n~ phần tử ~a_1, a_2, \dots, a_n~. Một dãy chỉ số ~1 \le i_1 < i_2 < \dots < i_k \le n~ mà ~a_{i_1} < a_{i_2} < \dots < a_{i_k}~, khi đó ~a_{i_1} < a_{i_2} < \dots < a_{i_k}~ được gọi là một dãy con tăng của ~A~. Hãy tìm độ dài dãy con tăng dài nhất của ~A~.

Input: Vào từ file văn bản LIS.INP:

• Dòng đầu ghi số nguyên dương ~n~ ~(n \le 10^5)~.
• Dòng hai ghi dãy số nguyên ~A~ ~(|A_i| \le 10^9)~.

Output: Ghi ra file văn bản LIS.OUT:

• Dòng 1: Một số nguyên là độ dài dãy con tăng đơn điệu dài nhất.
• Dòng 2: Dãy con tăng dài nhất tìm được, các số ghi cách nhau bởi dấu cách (Nếu có nhiều dãy thì ghi ra dãy có thứ tự từ điển nhỏ nhất)

Sample Input 1

6
1 2 5 4 6 2

Sample Output 1

4
1 2 4 6

Sample Input 2

10
1 2 5 4 6 2 1 2 3 4

Sample Output 2

4
1 2 3 4