1037: 最长上升子序列(hard)

Memory Limit:128 MB Time Limit:0.600 S
Judge Style:Text Compare Creator:
Submit:275 Solved:96

Description

给定一个长度为$n$的数组$a$,求其最长上升非降子序列的长度。 注意:子序列是不一定是连续的。

Input

第一行两个整数$n$。$(1 \le n \le 2 \times 10^5)$ 

接下来一行,$n$个整数表示$a_i$。$(1 \le a_i \le 10^9)$

Output

一个整数表示答案。 

Sample Input Copy

6
1 5 3 4 7 6

Sample Output Copy

4

HINT

解释:$[1, 3, 4, 7]$或$[1, 3, 4, 6]$长度为4。