Cho dãy \(A\) gồm \(N\) phần tử gồm các số nguyên dương \(A_1, A_2, ..., A_N\). Dãy \(C\) được gọi là dãy con đổi dấu độ dài \(K\) của dãy \(A\) nếu tồn tại dãy chỉ số:

• \(1 \leq i_1 < i_2 < ... < i_K \leq N\). Lúc này \(C_1 = A_{i_1}, C_2 = A_{i_2}, \dots, C_K = A_{i_K}\)
• Nếu \(K > 1\) thì \(C_1 > C_2 < C_3 > ...\) hoặc \(C_1 < C_2 > C_3 < ...\)

Yêu cầu: Tìm dãy con đổi dấu \(C\) với \(K\) lớn nhất có thể.

Input

• Dòng đầu tiên chứa số nguyên dương \(N\).
• Dòng thứ hai chứa \(N\) số nguyên dương \(A_1, A_2, ..., A_N\).

Output

• Dòng đầu tiên chứa số \(K\) là độ dài dãy con đổi dấu \(C\) dài nhất.
• Dòng thứ hai in ra \(K\) số nguyên dương \(C_1, C_2, ..., C_K\). Nếu có nhiều dãy \(C\) thoả mãn, in ra một dãy bất 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.
• Nếu in ra được số \(K\) là độ dài dãy con đổi dấu \(C\) dài nhất thì sẽ được \(50\%\) số điểm của test. Nếu in ra thêm được một dãy \(C\) tương ứng mà đúng thì sẽ được công thêm \(50\%\) số điểm của test.

Example

6
2 6 4 3 5 7 

4
2 4 3 5