{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003ch1\u003e\u003c/h1\u003e\n\u003cbr\u003e\n\n\u003cp\u003e\nFor a given sequence \u003cvar\u003eA \u003d {a\u003csub\u003e0\u003c/sub\u003e, a\u003csub\u003e1\u003c/sub\u003e, ... , a\u003csub\u003en-1\u003c/sub\u003e}\u003c/var\u003e, find the length of the longest increasing subsequnece (LIS) in \u003cvar\u003eA\u003c/var\u003e.\n\u003c/p\u003e\n\n\u003cp\u003e\nAn increasing subsequence of \u003cvar\u003eA\u003c/var\u003e is defined by a subsequence \u003cvar\u003e{a\u003csub\u003ei\u003csub\u003e0\u003c/sub\u003e\u003c/sub\u003e, a\u003csub\u003ei\u003csub\u003e1\u003c/sub\u003e\u003c/sub\u003e, ... , a\u003csub\u003ei\u003csub\u003ek\u003c/sub\u003e\u003c/sub\u003e}\u003c/var\u003e where \u003cvar\u003e0 ≤ i\u003csub\u003e0\u003c/sub\u003e \u0026lt; i\u003csub\u003e1\u003c/sub\u003e \u0026lt; ... \u0026lt; i\u003csub\u003ek\u003c/sub\u003e \u0026lt; n\u003c/var\u003e and \u003cvar\u003ea\u003csub\u003ei\u003csub\u003e0\u003c/sub\u003e\u003c/sub\u003e \u0026lt; a\u003csub\u003ei\u003csub\u003e1\u003c/sub\u003e\u003c/sub\u003e \u0026lt; ... \u0026lt; a\u003csub\u003ei\u003csub\u003ek\u003c/sub\u003e\u003c/sub\u003e.\n\u003c/var\u003e\u003c/p\u003e\n\n\n\u003ch2\u003eInput\u003c/h2\u003e\n\n\u003cpre\u003e\u003cvar\u003en\u003c/var\u003e\n\u003cvar\u003ea\u003csub\u003e0\u003c/sub\u003e\u003c/var\u003e\n\u003cvar\u003ea\u003csub\u003e1\u003c/sub\u003e\u003c/var\u003e\n:\n\u003cvar\u003ea\u003csub\u003en-1\u003c/sub\u003e\u003c/var\u003e\n\u003cvar\u003e\n\u003c/var\u003e\u003c/pre\u003e\n\n\u003cp\u003e\nIn the first line, an integer \u003cvar\u003en\u003c/var\u003e is given. In the next \u003cvar\u003en\u003c/var\u003e lines, elements of \u003cvar\u003eA\u003c/var\u003e are given.\n\u003c/p\u003e\n\n\u003ch2\u003eOutput\u003c/h2\u003e\n\n\u003cp\u003e\nThe length of the longest increasing subsequence of \u003cvar\u003eA\u003c/var\u003e.\n\u003c/p\u003e\n\n\u003ch2\u003eConstraints\u003c/h2\u003e\n\n\u003cul\u003e\n\u003cli\u003e1 ≤ \u003cvar\u003en\u003c/var\u003e ≤ 100000\u003c/li\u003e\n\u003cli\u003e0 ≤ \u003cvar\u003ea\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e ≤ 10\u003csup\u003e9\u003c/sup\u003e\u003c/li\u003e\n\u003c/ul\u003e\n\n\u003ch2\u003eSample Input 1\u003c/h2\u003e\n\u003cpre\u003e5\n5\n1\n3\n2\n4\n\u003c/pre\u003e\n\u003ch2\u003eSample Output 1\u003c/h2\u003e\n\u003cpre\u003e3\n\u003c/pre\u003e\n\u003cbr\u003e\n\n\n\u003ch2\u003eSample Input 2\u003c/h2\u003e\n\u003cpre\u003e3\n1\n1\n1\n\u003c/pre\u003e\n\u003ch2\u003eSample Output 2\u003c/h2\u003e\n\u003cpre\u003e1\n\u003c/pre\u003e\n\u003cbr\u003e"}}]}