小波喜歡美食,他總共會遇到 $N$ 道依序上菜的美食,小波可以選擇其中的一些來品嚐。每道菜都有一個正整數的美味值,而小波希望他品嚐的每一道菜都嚴格比之前品嚐的菜更美味。
舉例而言,如果有 $5$ 道菜分別有美味值 $7,8,8,9,4$,則小波可以品嚐第 $1, 2, 4$ 道菜,分別有美味值 $7, 8, 9$。但小波不能品嚐第 $2,3,4$ 道菜,因為第 $3$ 道菜並沒有比第 $2$ 道菜更加美味。
給一個上菜的序列,想請問小波最多能品嚐幾道菜。
輸入第一行是一個整數 $N$,代表一共有幾道菜。
輸入第二行是 $N$ 個以空白分隔的整數 $a_i$,依序代表美食的美味值。
輸入保證 $1\le N\le 5000$,$1\le a_i\le 10^ 9$。
輸出一行一個整數,代表在適當安排下,小波最多可以吃到幾道菜。
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~1 | 範例測資 | 0 |
2 | 0~16 | 無額外限制 | 100 |