Replace Sort#13024

Replace Sort

3 seconds
256 megabytes
Very hard

Consider an array and a set of integers such that all numbers in and are distinct. Your task is to turn into a sorted array. To do this you can take any number from and replace any element of with it. You can perform this operation any number of times, but each element of can be used at most once.

Determine the minimum number of operations needed to turn into a sorted array, or determine that it is impossible.

Input

The first line of input contains two integers and (1 \le N, M \le 5 \cdot 10^5) — the sizes of and respectively.

The second line contains integers A_1, A_2, \ldots, A_N.

The third line contains integers B_1, B_2, \ldots, B_M.

All the (N + M) elements are distinct, positive and do not exceed 10^9.

Output

If it is impossible to turn into a sorted array, print . Otherwise, print the minimum number of operations needed.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Example 3

Loading
Loading

Note

In all three examples, the issue is that 13 > 10, so we have to change at least one of them.

In the first one, we can decrease by replacing it with , but it breaks the other side, so there is no solution.

In the second one, we also have , which we can use to fix the broken side. It is impossible to do with less than operations.

In the third example we can finally increase the last element, thus fixing in 1 operation.