{"raw_statement":[{"iden":"problem statement","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."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 10^5$\n*   $0 \\leq A_i \\leq 10^9$"},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$A_1$\n$:$\n$A_N$"},{"iden":"sample input 1","content":"5\n2\n1\n4\n5\n3"},{"iden":"sample output 1","content":"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."},{"iden":"sample input 2","content":"4\n0\n0\n0\n0"},{"iden":"sample output 2","content":"4\n\nWe have to paint all the integers with distinct colors."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}