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\).
• Nếu \(K > 1\) thì \(C_{i_1} > C_{i_2} < C_{i_3} > ...\) hoặc \(C_{i_1} < C_{i_2} > C_{i_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