TopCoder

User's AC Ratio

100.0% (12/12)

Submission's AC Ratio

83.3% (15/18)

Tags

Description

小波喜歡美食,他總共會遇到 $N$ 道依序上菜的美食,小波可以選擇其中的一些來品嚐。每道菜都有一個正整數的美味值,而小波希望他品嚐的每一道菜都嚴格比之前品嚐的菜更美味。

舉例而言,如果有 $5$ 道菜分別有美味值 $7,8,8,9,4$,則小波可以品嚐第 $1, 2, 4$ 道菜,分別有美味值 $7, 8, 9$。但小波不能品嚐第 $2,3,4$ 道菜,因為第 $3$ 道菜並沒有比第 $2$ 道菜更加美味。

給一個上菜的序列,想請問小波最多能品嚐幾道菜。

Input Format

輸入第一行是一個整數 $N$,代表一共有幾道菜。

輸入第二行是 $N$ 個以空白分隔的整數 $a_i$,依序代表美食的美味值。

輸入保證 $1\le N\le 5000$,$1\le a_i\le 10^ 9$。

Output Format

輸出一行一個整數,代表在適當安排下,小波最多可以吃到幾道菜。

Sample Input 1

5
7 8 8 9 4

Sample Output 1

3

Sample Input 2

10
1 3 9 2 4 5 6 10 7 8

Sample Output 2

7

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~16 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
14 1000 524288 65536 2
15 1000 524288 65536 2
16 1000 524288 65536 2