Longest Non-Decreasing Subsequence

You are given a sequence of integers. Your task is to determine the length of the longest subsequence such that the elements of the subsequence are in non-decreasing order. In other words, for any two consecutive elements in the subsequence, the later element is greater than or equal to the former. This problem can be efficiently solved using dynamic programming.

The relation used in the dynamic programming approach is given by:

\(dp[i] = \max_{0 \leq j < i \text{ and } a[i] \geq a[j]}\{dp[j]\} + 1\)

If the sequence is empty, the answer is 0.

inputFormat

The input is given via standard input. The first line contains a single integer (n) ((0 \le n \le 10^5)), representing the number of elements in the sequence. If (n > 0), the second line contains (n) space-separated integers representing the sequence.

outputFormat

Output a single integer on standard output: the length of the longest non-decreasing subsequence.## sample

5
3 10 2 1 20

3