TopCoder

Thumb asuna
Leo

User's AC Ratio

65.8% (25/38)

Submission's AC Ratio

36.1% (35/97)

Tags

Description

李胖喜歡出題,更喜歡判斷一些題目是好的還是壞的
他判斷的方法是量化每個題目的難易度,用數字來表示
某次考試輪到李胖出題了,他從他大量的題庫中希望出越多題越好,可是又不希望改變題目的先後順序,還希望這些題目是好的
所謂好的題目的判斷如下:
對於一個題目序列$A$,若每個$i,j$符合$i<j$且$A_i<A_j$,則這些題目是好的
簡單來說就是不要出現任何難易程度逆序的題目
現在給你代表李胖題庫的序列$P$,求出李胖最多能出幾題?

Input Format

輸入第一行為正整數$N,N\le 1000000$,代表李胖題庫的題目數
接著第二行包含$N$個正整數$P_1,P_2,\ldots ,P_N$,代表題庫中每一題的難易程度

Output Format

輸出李胖最多能出的題數

Sample Input

5
1 2 3 4 5

Sample Output

5

Hints

Problem Source

Problem Set By waynetu

Subtasks

For Testdata: 0 ~ 1, Score: 10
For Testdata: 2 ~ 3, Score: 20
For Testdata: 4 ~ 7, Score: 30
For Testdata: 0 ~ 9, Score: 40
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 65536
1 1000 65536 65536
2 1000 65536 65536
3 1000 65536 65536
4 1000 65536 65536
5 1000 65536 65536
6 1000 65536 65536
7 1000 65536 65536
8 1000 65536 65536
9 1000 65536 65536