← 返回 amazon 的题目列表Maximum number of dominoes that can be removed
类型:online_judge
amazon
Amazon Games has recently launched a new game. The game consists of n dominoes where the i-th one has some score domino[i] and has an order which is defined as the longest strictly increasing subsequence of the scores of the dominoes. In the i-th move, the player can remove the domino remove[i]. Given the arrays domino and remove, find the maximum number of moves such that the order of remaining dominoes is at least equal to a given integer min_order.
Example
Input: n = 6, domino = [1, 4, 4, 2, 5, 3], remove = [2, 1, 4, 0, 5, 3], min_order = 3
Output: 3
Constraints
1 ≤ n ≤ 10^5
0 ≤ domino[i] ≤ 10^9
0 ≤ remove[i] ≤ n - 1
Example
Input
6
1 4 4 2 5 3
2 1 4 0 5 3
3