Longest Increasing Subsequence

Given a sequence of integers, your task is to determine the length of its longest increasing subsequence (LIS). An increasing subsequence is a subset of the array (not necessarily contiguous) where each element is strictly larger than its predecessor. Formally, for a subsequence (a_{i_1}, a_{i_2}, \dots, a_{i_k}) with (i_1 < i_2 < \dots < i_k), it must hold that (a_{i_1} < a_{i_2} < \dots < a_{i_k}).

You will read the input from standard input (stdin) and output the result to standard output (stdout).

inputFormat

The first line contains an integer (n), representing the number of elements in the sequence. The second line contains (n) space-separated integers. If (n = 0), no further input is provided.

outputFormat

Output a single integer: the length of the longest increasing subsequence in the given sequence.## sample

6
10 22 9 33 21 50

4