{"code":"dplis6","name":"Dãy đổi dấu","description":"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ố:\r\n+ $1 \\leq i_1 < i_2 < ... < i_K \\leq N$.\r\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} < ...$\r\n\r\n**Yêu cầu**: Tìm dãy con đổi dấu $C$ với $K$ lớn nhất có thể.\r\n\r\n####Input\r\n+ Dòng đầu tiên chứa số nguyên dương $N$.\r\n+ Dòng thứ hai chứa $N$ số nguyên dương $A_1, A_2, ..., A_N$.\r\n\r\n####Output\r\n+ Dòng đầu tiên chứa số $K$ là độ dài dãy con đổi dấu $C$ dài nhất.\r\n+ 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ỳ. \r\n\r\n####Constraints\r\n- $N\\leq 10^5$\r\n- $A_i \\leq 10^9$\r\n\r\n####Scoring\r\n- Subtask $1$ ($50\\%$ số điểm): $N\\leq 10^3$.\r\n- Subtask $2$ ($50\\%$ số điểm): Không có ràng buộc gì thêm.\r\n- 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.\r\n\r\n####Example\r\n\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        6\r\n        2 6 4 3 5 7 \r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        4\r\n        2 4 3 5\r\n        ```","points":400.0,"partial":true,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}