Cargo Stack Priority Recall

EasyArrayHash setSimulationCounting2 sample tests5 hidden tests

A column of shipping containers sits on a dock, described bottom-to-top by an array of positive integer labels. Dockworkers can only lift containers off the very top of the stack, one at a time, and each lift is logged as one removal. A shipment manifest requires recovering at least one container bearing each label from 1 through k before the crew can move on. Given the bottom-to-top label order and the integer k, compute the minimum number of top removals needed so that every label in 1..k has been removed at least once. It is guaranteed that each label from 1 to k appears somewhere in the stack.

Input format

Line 1: two space-separated integers n and k -- n is the number of containers, k is the highest required label.
Line 2: n space-separated integers arr[0..n-1], the container labels listed from the bottom of the stack to the top.

Output format

Print a single integer: the minimum number of top removals required.

Constraints

1 <= n <= 1000
1 <= k <= n
1 <= arr[i] <= n
Every integer in [1, k] occurs at least once in arr.

Examples

Example 1

Input

5 3
4 3 2 5 1

Expected

Explanation

Bottom-to-top the stack is [4,3,2,5,1], so removals proceed from the top: 1 (removal 1, collected {1}), 5 (removal 2, not needed since k=3), 2 (removal 3, collected {1,2}), 3 (removal 4, collected {1,2,3} -- done). The answer is 4.

Example 2

Input

5 5
4 3 2 5 1

Expected

Explanation

Now every label 1..5 is required. Label 4 sits at the very bottom of the stack (index 0), so the entire stack of 5 containers must be removed before it is recovered. The answer is 5.

Ready to solve this?