Longest Non-decreasing Subsequence

You are given a sequence of integers representing the altitudes of mountain peaks. Your task is to determine the length of the longest non-decreasing subsequence that can be extracted from this sequence. A subsequence is obtained by deleting some or no elements from the original array without changing the order of the remaining elements.

The problem can be formulated as follows: for an array \(a[1 \dots n]\), find the maximum \(L\) such that there exists indices \(1 \le i_1 < i_2 < \dots < i_L \le n\) with \(a[i_1] \le a[i_2] \le \dots \le a[i_L]\). This can be computed using a dynamic programming approach where \(dp[i] = \max_{j < i \text{ and } a[i] \ge a[j]} (dp[j]) + 1\), and the final answer is \(\max_i dp[i]\).

inputFormat

The input consists of multiple test cases. Each test case starts with an integer \(n\) representing the number of peaks. The next line contains \(n\) space-separated integers which denote the peak altitudes. Processing terminates when a test case with \(n=0\) is encountered, which should not be handled.

outputFormat

For every test case, print one line containing the length of the longest non-decreasing subsequence.

6
5 3 4 8 6 7
5
1 2 3 3 2
0

4
4