Longest Non-Decreasing Subsequence

Given a sequence of integers, your task is to determine the length of the longest non-decreasing subsequence. A subsequence is derived from the original sequence by deleting some or no elements without changing the order of the remaining elements.

For example, given the sequence ( [10, 22, 9, 33, 21, 50, 41, 60, 80] ), one of the longest non-decreasing subsequences is ( [10, 22, 33, 50, 60, 80] ) which has a length of 6.

inputFormat

Input is given via standard input and consists of multiple lines. Each line contains a space-separated list of integers representing a sequence. The input terminates with a line containing a single 0, which should not be processed.

outputFormat

For each test case (each input line before the terminating 0), output the length of the longest non-decreasing subsequence on a separate line, using standard output.## sample

1 2 3 4
4 3 2 1
10 22 9 33 21 50 41 60 80
0

4
1
6