← 返回题目列表

Codeforces · 1437/E

E. 使其增加

中文机器翻译题面 查看原题

给你一个 $$$n$$$ 整数数组 $$$a_1$$$、$$$a_2$$$、...、$$$a_n$$$,以及一组 $$$b$$$ 的 $$$k$$$ 不同整数,从 $$$1$$$ 到 $$$n$$$。

在一次操作中,您可以选择两个整数 $$$i$$$ 和 $$$x$$$($$$1 \le i \le n$$$,$$$x$$$ 可以是任何整数)并分配 $$$a_i := x$$$。仅当 $$$i$$$ 不属于集合 $$$b$$$ 时才可以执行此操作。

计算应执行的最小操作数,以使数组 $$$a$$$ 递增(即 $$$a_1 < a_2 < a_3 < \dots < a_n$$$),或报告这是不可能的。

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 5 \cdot 10^5$$$, $$$0 \le k \le n$$$) — 分别是数组 $$$a$$$ 和集合 $$$b$$$ 的大小。

第二行包含 $$$n$$$ 整数 $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i \le 10^9$$$)。

然后,如果 $$$k \ne 0$$$,则第三行包含 $$$k$$$ 整数 $$$b_1$$$, $$$b_2$$$, ..., $$$b_k$$$ ($$$1 \le b_1 < b_2 < \dots < b_k \le n$$$)。如果 $$$k = 0$$$,则跳过此行。

输出

如果使用给定的操作不可能使数组 $$$a$$$ 增加,则打印 $$$-1$$$。

否则,打印一个整数 — 您必须执行的最少操作数。

示例

输入 #1

7 2
1 2 1 1 3 5 1
3 5

输出 #1

4

输入 #2

3 3
1 3 2
1 2 3

输出 #2

-1

输入 #3

5 0
4 3 1 2 3

输出 #3

2

输入#4

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

输出#4

3