Background

最长上升子序列（Longest Increasing Subsequence）

Description

给你一串数，找它的最长上升子序列。

Format

Input

第一行是序列的长度n (1 <= n <= 1000)，第二行是序列中n个小于90000的整数。

Output

最长上升子序列的长度。

Sample 1

Input

7
1 7 3 5 9 4 8

Output

4

Hint

（DP不好写，出道~~简单的~~模板题）