Longest Non-Decreasing Subsequence

Difficulty: 1600 5000 ms 128 MB

dp binary-search

Find the length of the longest non-decreasing subsequence (equal values may be consecutive in the subsequence).

Input: the first line has N; the second line has the array.

Output: the length.

Constraints:

• 1 ≤ N ≤ 10⁵
• 1 ≤ a_i ≤ 10⁹

Sample Tests

5
1 2 2 3 3

5

1
7

1

4
4 4 4 4

4

Read the Editorial