题目描述

在序列 $a_1,a_2,\ldots,a_n$ 中，一个长度为 $k$ 的子序列是指 $a_{i_1},a_{i_2},\ldots,a_{i_k}$，其中 $1\le i_1<i_2<\cdots<i_k\le n$。

如果 $a_{i_1}<a_{i_2}<\cdots<a_{i_k}$，请输出 $k$ 的最大值，即数组 $a$ 的最长上升子序列长度。

输入格式

第一行，一个正整数 $n$，表示数组中的元素个数。

第二行，$n$ 个用空格隔开的正整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出一个正整数，表示最长上升子序列的长度。

输入输出样例

输入 #1

12
35 42 4 12 29 21 29 11 1 42 43 49

输出 #1

7

数据范围

• 对于 $60\%$ 的数据，$10\le n\le 1000$，$1\le a_i\le 1000$；
• 对于全部数据，$10\le n\le 100000$，$1\le a_i\le 10^9$。

12
35 42 4 12 29 21 29 11 1 42 43 49

7

25
97117714 294928619 366980078 256969707 312818318 256539714 538905405 405592370 287071449 246581026 851258672 142432285 257282094 832994716 790031373 89321086 585600337 314545328 57141723 404821482 280047556 60660976 262372275 275255685 845647467

6

63
55583557 548897323 71436624 410653921 803629861 188076073 17527802 466173033 424737122 313481919 582324110 229113623 779407074 50735752 425390887 191120015 191710241 574035076 807614760 851472207 59501496 889651733 721187744 306862850 635804486 640190536 236664554 281208958 641115394 624210370 451555366 698196488 978172066 525050838 816709358 222379986 537917134 695093813 50948829 537075870 34751574 59129509 208149738 568327870 963727236 923707417 392908568 196268475 370018547 326040018 888390295 284083472 205997281 336858846 943535822 601418206 292468087 238701245 473564857 70285688 776072165 363676829 503441765

13