Longest Increasing Subsequence

Given a sequence of integers, your task is to find the length of the longest strictly increasing subsequence. A subsequence is a sequence derived from the original sequence by deleting some or no elements without changing the order of the remaining elements. Formally, for a sequence (a_1, a_2, \dots, a_n), a subsequence (a_{i_1}, a_{i_2}, \dots, a_{i_k}) (with (1 \le i_1 < i_2 < \dots < i_k \le n)) is strictly increasing if (a_{i_1} < a_{i_2} < \dots < a_{i_k}). Your goal is to determine the maximum possible value of (k).

inputFormat

The input is given via standard input (stdin). The first line contains an integer (n) representing the number of elements in the sequence. If (n > 0), the second line contains (n) space-separated integers.

outputFormat

Output a single integer to standard output (stdout) representing the length of the longest strictly increasing subsequence.## sample

7
10 22 9 33 21 50 41

4