Trim to Non-Decreasing

Difficulty: 1600 4000 ms 128 MB

dp binary-search

Print the minimum number of elements to delete so the remaining array is non-decreasing.

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

Output: N minus the longest non-decreasing subsequence length.

Constraints:

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

Sample Tests

5
3 1 2 1 4

2

3
1 1 1

0

Read the Editorial