Code Submission Evaluation System Login

CSES Problem Set

Increasing Subsequence


Task | Statistics


CSES - Increasing Subsequence

Time limit:1.00 s Memory limit:512 MB

You are given an array that contains $n$ integers. Your task is to determine the longest increasing subsequence in the array.

An increasing subsequence is a set of values in the array in their original order such that each number is larger than the previous number.

Input

The first line contains an integer $n$: the size of the array.

After this there are $n$ integers $x_1,x_2,\ldots,x_n$: the contents of the array.

Output

Print the length of the longest increasing subsequence.

Constraints
Example

Input:
8
7 3 5 3 6 2 9 8


Output:
4