Longest Increasing Subsequence

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

You are given a sequence of \(n\) integers \(a_i\). Your task is to find the length of the longest increasing subsequence of the given sequence. A sequence \(x\) is called a subsequence of a sequence \(y\) if some elements (possibly zero) can be deleted from \(y\) to leave the sequence \(x\).

Input

The first line contains an integer \(n\).

The next line contains \(n\) integers — the sequence \(a_i\).

Output

Output the length of the longest increasing subsequence.

Constraints

\(1 \le n \le 100\),

\(1 \le a_i \le 10^9\).

Samples

Input (stdin) сopy	Output (stdout) сopy
5 4 7 2 10 3	3

Notes

In the example, the longest increasing subsequence is [4, 7, 10].