#P1437E. Make It Increasing

    ID: 571 远端评测题 2000ms 256MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>binary searchconstructive algorithmsdata structuresdpimplementation*2200

Make It Increasing

Description

You are given an array of $n$ integers $a_1$, $a_2$, ..., $a_n$, and a set $b$ of $k$ distinct integers from $1$ to $n$.

In one operation, you may choose two integers $i$ and $x$ ($1 \le i \le n$, $x$ can be any integer) and assign $a_i := x$. This operation can be done only if $i$ does not belong to the set $b$.

Calculate the minimum number of operations you should perform so the array $a$ is increasing (that is, $a_1 < a_2 < a_3 < \dots < a_n$), or report that it is impossible.

The first line contains two integers $n$ and $k$ ($1 \le n \le 5 \cdot 10^5$, $0 \le k \le n$) — the size of the array $a$ and the set $b$, respectively.

The second line contains $n$ integers $a_1$, $a_2$, ..., $a_n$ ($1 \le a_i \le 10^9$).

Then, if $k \ne 0$, the third line follows, containing $k$ integers $b_1$, $b_2$, ..., $b_k$ ($1 \le b_1 < b_2 < \dots < b_k \le n$). If $k = 0$, this line is skipped.

If it is impossible to make the array $a$ increasing using the given operations, print $-1$.

Otherwise, print one integer — the minimum number of operations you have to perform.

Input

The first line contains two integers $n$ and $k$ ($1 \le n \le 5 \cdot 10^5$, $0 \le k \le n$) — the size of the array $a$ and the set $b$, respectively.

The second line contains $n$ integers $a_1$, $a_2$, ..., $a_n$ ($1 \le a_i \le 10^9$).

Then, if $k \ne 0$, the third line follows, containing $k$ integers $b_1$, $b_2$, ..., $b_k$ ($1 \le b_1 < b_2 < \dots < b_k \le n$). If $k = 0$, this line is skipped.

Output

If it is impossible to make the array $a$ increasing using the given operations, print $-1$.

Otherwise, print one integer — the minimum number of operations you have to perform.

Samples

7 2
1 2 1 1 3 5 1
3 5
4
3 3
1 3 2
1 2 3
-1
5 0
4 3 1 2 3
2
10 3
1 3 5 6 12 9 8 10 13 15
2 4 9
3