Background

经典问题，适合初学者，^_^

Description

给定一个长度为 $n (n \leq 10^6)$ 的序列 $a$，求出 $a$ 最长的子序列使得这个子序列是严格单调递增的。
子序列是指从原序列中删除任意个元素（可以不删除）后，保持原有顺序得到的序列。

Format

Input

第一行一个整数 $n$，表示序列长度。
第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$，整数之间用空格分隔，满足 $|a_i| \leq 10^9$。

Output

一行一个整数，表示最长严格上升子序列的长度。

Samples

6
1 3 2 4 5 0

4