{"code":"dplis7","name":"Dãy con tăng dài nhất 2","description":"Cho dãy $(A, B)$ gồm $N$ phần tử là các cặp số nguyên $A_1, A_2, ..., A_N$ và $B_1, B_2, ..., B_N$. Dãy $(C, D)$ được gọi là dãy con tăng độ dài $K$của dãy $(A, B)$ nếu thoả mãn các điều kiện sau:\r\n+ $K \\geq 1$.\r\n+ $1 \\leq i_1 < i_2 < i_3 < ... < i_K \\leq N$.\r\n+ $C_1 = A_{i_1}, C_2 = A_{i_2}, ..., C_K = A_{i_K}$.\r\n+ $D_1 = B_{i_1}, D_2 = B_{i_2}, ..., D_K = B_{i_K}$.\r\n+ $C_1 < C_2 < ... < C_K$ nếu $K \\geq 2$.\r\n+ $D_1 < D_2 < ... < D_K$ nếu $K \\geq 2$.\r\n\r\n**Yêu cầu**: Tìm dãy $(C, D)$ thoả mãn $K$ lớn nhất có thể, tức là tìm dãy con $(C, D)$ dài nhất.\r\n\r\n## Input\r\nGồm $N + 1$ dòng:\r\n+ Dòng thứ nhất gồm số nguyên dương $N$.\r\n+ $N$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên ($A_i, B_i$). $(|A_i|, |B_i| \\leq 10^9)$.\r\n\r\n## Output\r\nGồm $K+1$ dòng: \r\n+ Dòng đầu tiên in ra số $K$ là độ dài dãy con $(C, D)$ dài nhất. \r\n+ $K$ dòng tiếp theo, dòng thứ $i$ in ra hai số nguyên $C_i, D_i$ là dãy có độ dài $K$ dài nhất.\r\n\r\n## Scoring\r\n+ Subtask $1$ ($25\\%$ số điểm): $N \\leq 10^3$.\r\n+ Subtask $2$ ($25\\%$ số điểm): $N \\leq 10^5$, $|A_i|, |B_i| \\leq 10^3$.\r\n+ Subtask $3$ ($25\\%$ số điểm): $N \\leq 10^5$.\r\n+ Subtask $4$ ($25\\%$ số điểm): $N \\leq 5.10^5$.\r\n+ Nếu xuất đúng số $K$ sẽ được $50\\%$ số điểm của test. Nếu xuất thêm đúng dãy $(C, D)$ tương ứng thì sẽ được thêm $50\\%$ số điểm của test.\r\n\r\n## Example\r\n\r\n!!! question \"Test 1\"\r\n\r\n    ???+ \"Input\"\r\n        ```sample\r\n        5\r\n        1 5\r\n        2 3\r\n        4 5\r\n        6 8\r\n        9 9\r\n        ```\r\n    \r\n    ???+ success \"Output\"\r\n        ```sample\r\n        4\r\n        2 3\r\n        4 5\r\n        6 8\r\n        9 9\r\n        ```","points":500.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}}