Cho dãy \(A\) gồm \(N\) phần tử là các số nguyên dương \(A_1, A_2, ..., A_N\). Dãy \(C\) được gọi là dãy con tăng độ dài \(K\) của \(A\) nếu thoả mãn các điều kiện sau:

• \(K \geq 1\).
• \(1 \leq i_1 < i_2 < i_3 < ... < i_K \leq N\).
• \(C_1 = A_{i_1}, C_2 = A_{i_2}, ..., C_K = A_{i_K}\).
• \(C_1 < C_2 < ... < C_K\) nếu \(K \geq 2\)

Yêu cầu: Tìm dãy \(C\) sao cho độ dài \(K\) lớn nhất có thể. Nếu có nhiều dãy \(C\) thoả mãn, in ra dãy có thứ tự từ điển nhỏ nhất. Dãy \(C\) được gọi là dãy có thứ tự từ điển nhỏ hơn dãy \(C'\) nếu tồn tại chỉ số \(p\) \((p \geq 1)\) thoả mãn các điều kiện sau:

• \(C_1 = C'_1\), \(C_2 = C'_2\), \(...\), \(C_{p-1} = C'_{p-1}\) nếu \(p > 1\).
• \(C_p < C'_p\).

Input

• Dòng thứ nhất gồm số nguyên dương \(N\).
• Dòng thứ hai gồm \(N\) số nguyên dương \(A_1, A_2, ..., A_N\).

Output

• Dòng thứ nhất in ra số \(K\) là độ dài dãy con tăng \(C\) dài nhất.
• Dòng thứ hai in ra \(K\) số nguyên dương \(C_1, C_2, ..., C_N\) là dãy có thứ tự từ điển nhỏ nhất độ dài \(K\).

Constraints

• \(N \leq 10^5\)
• \(|A_i| \leq 10^9\)

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(N\leq 10^3\).
• Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

5
1 3 5 4 6 

4
1 3 4 6