Longest Non-Decreasing Tree Sequence

You are given a row of trees, each with a certain height. Your task is to select a subset of these trees such that their heights form a non-decreasing sequence (i.e. each tree is not shorter than the previous one).

This problem is a variation of the Longest Non-Decreasing Subsequence problem. The objective is to maximize the number of trees you can keep while maintaining the order. A common dynamic programming approach can be used to solve this problem, where the recurrence relation is given by:

$dp[i] = \max_{0 \le j < i \text{ and } h_i \ge h_j}\{dp[j] + 1\}$

Here, $dp[i]$ denotes the length of the longest non-decreasing sequence that ends at the i-th tree. Your job is to compute the maximum value of $dp[i]$ for all valid indices i.

inputFormat

The input is given via standard input (stdin). The first line contains an integer n representing the number of trees. The second line contains n space-separated integers which represent the heights of the trees.

outputFormat

Output a single integer via standard output (stdout), indicating the maximum number of trees that can form a non-decreasing sequence.## sample

5
3 4 2 6 1

3