Longest Non-decreasing Subsequence Length

You are given an integer N and a sequence of N integers A₁, A₂, \( \dots \), A_N. Your task is to determine the length of the longest non-decreasing subsequence of the given sequence.

A subsequence is a sequence that can be derived from the original sequence by deleting some or no elements without changing the order of the remaining elements. Formally, if \( \{i_1, i_2, \dots, i_k\} \) with \(1 \le i_1 < i_2 < \dots < i_k \le N\) are the indices of the chosen elements, then the subsequence \( A_{i_1}, A_{i_2}, \dots, A_{i_k}\) is non-decreasing if and only if \( A_{i_1} \le A_{i_2} \le \dots \le A_{i_k} \).

For example, given the input sequence [5, 3, 4, 8, 6], one possible longest non-decreasing subsequence is [3, 4, 8] and its length is 3.

inputFormat

The first line contains an integer N (\( 0 \le N \le 10^5 \)), representing the number of elements in the sequence.

The second line contains N space-separated integers \( A_1, A_2, \dots, A_N \) where each \( A_i \) is the ith element of the sequence.

outputFormat

Output a single integer representing the length of the longest non-decreasing subsequence of the given sequence.

## sample

5
5 3 4 8 6

3

</p>