Question
Make Increasing Sequence
You are given an array
Your task is to find the minimum number of elements that need to be removed so that the remaining array becomes sorted in non-decreasing order.
nums consisting of n integers. You are allowed to remove some elements (possibly none) from the array.Your task is to find the minimum number of elements that need to be removed so that the remaining array becomes sorted in non-decreasing order.
Input
The first line contains a single integer KaTeX can only parse string typed expression — the size of the array.
The second line contains KaTeX can only parse string typed expression integers, representing the elements of the array — KaTeX can only parse string typed expression.
The second line contains KaTeX can only parse string typed expression integers, representing the elements of the array — KaTeX can only parse string typed expression.
Output
Print a single integer — the minimum number of elements to remove to make the array sorted.
Example
Input
5
3 2 6 4 5
Output
2
Explanation
One way to make the array sorted is to remove KaTeX can only parse string typed expression and KaTeX can only parse string typed expression, leaving KaTeX can only parse string typed expression, which is non-decreasing.
5
3 2 6 4 5
Output
2
Explanation
One way to make the array sorted is to remove KaTeX can only parse string typed expression and KaTeX can only parse string typed expression, leaving KaTeX can only parse string typed expression, which is non-decreasing.