Longest Increasing Subsequence

This problem requires you to compute the length of the longest strictly increasing subsequence from a sequence of integers. For each test case, you will be given an integer n representing the number of elements in the sequence, followed by n space-separated integers. The input terminates when n = 0 is encountered.

The longest increasing subsequence (LIS) can be defined using the recurrence: $$ \text{lis}[i] = \max\left(1,\; \max_{\substack{0 \leq j a[j]}} (\text{lis}[j] + 1)\right) $$ The answer for each test case is the maximum value in the lis array.

inputFormat

The input consists of multiple test cases. Each test case begins with a line containing a single integer n (the number of elements in the sequence). The next line contains n space-separated integers. The sequence of test cases is terminated by a test case with n = 0, which should not be processed.

Input is provided via stdin.

outputFormat

For each test case, output a single integer representing the length of the longest increasing subsequence found in the sequence. Each answer should be printed on a new line, and output is to be written to stdout.

## sample

6
10 22 9 33 21 50
5
3 10 2 1 20
0

4
3

</p>