{"problem":{"name":"Sequence Decomposing","description":{"content":"You are given a sequence with $N$ integers: $A = { A_1, A_2, \\cdots, A_N }$. For each of these $N$ integers, we will choose a color and paint the integer with that color. Here the following condition ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc134_e"},"statements":[{"statement_type":"Markdown","content":"You are given a sequence with $N$ integers: $A = { A_1, A_2, \\cdots, A_N }$. For each of these $N$ integers, we will choose a color and paint the integer with that color. Here the following condition must be satisfied:\n\n*   If $A_i$ and $A_j$ $(i < j)$ are painted with the same color, $A_i < A_j$.\n\nFind the minimum number of colors required to satisfy the condition.\n\n## Constraints\n\n*   $1 \\leq N \\leq 10^5$\n*   $0 \\leq A_i \\leq 10^9$\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$A_1$\n$:$\n$A_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc134_e","tags":[],"sample_group":[["5\n2\n1\n4\n5\n3","2\n\nWe can satisfy the condition with two colors by, for example, painting $2$ and $3$ red and painting $1$, $4$, and $5$ blue."],["4\n0\n0\n0\n0","4\n\nWe have to paint all the integers with distinct colors."]],"created_at":"2026-03-03 11:01:14"}}