Removal Sorting

Points: 1
Time limit: 2.0s
Memory limit: 512M

Author:
Problem types

You have a zero-indexed array, $$A$$, containing positive integers, and a permutation of the indexes for that array, $$D$$. You plan to go through $$D$$ in order, and mark the corresponding element in $$A$$ as deleted. Note that you won't then move elements of $$A$$ down after deletion, so elements keep their original indexes throughout this process. For example, consider $$A = \{ 2, 1, 8, 3 \}$$ and $$D = \{ 1, 3, 0, 2 \}$$.

2, 1, 8, 3

Then index 1 is marked as deleted,

2, x, 8, 3

Then index 3,

2, x, 8, x

Then 0,

x, x, 8, x

Finally 2,

x, x, x, x

After which deletion is $$A$$ first sorted in monotonically ascending order? In our example, it is sorted after the second deletion, since (ignoring deleted elements) 2, 8 is sorted.

Input Specification

The first line contains a single integer, the size of $$A$$ ($$1 \leq |A| \leq 10^5$$). The next line contains $$|A|$$ space separated integers in the inclusive range from $$1$$ to $$10^9$$. The next line also contains $$|A|$$ space separated integers, these are the elements of $$D$$, and are a permutation of $$\{ 0, 1, \dots , |A|-1 \}$$.

Output Specification

Output a single integer. The minimum number of deletions after which $$A$$ is sorted.

4
2 1 8 3
1 3 0 2

2