31152번 - Replace Sort 다국어

문제

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

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

입력

The first line of input contains two integers $N$ and $M$ (1ドル \le N, M \le 5 \cdot 10^5$) --- the sizes of $A$ and $B$ respectively.

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

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

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

출력

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

제한

노트

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 13ドル$ by replacing it with 5ドル,ドル but it breaks the other side, so there is no solution.

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

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