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.


-----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.


-----Examples-----
Input
7 2
1 2 1 1 3 5 1
3 5

Output
4

Input
3 3
1 3 2
1 2 3

Output
-1

Input
5 0
4 3 1 2 3

Output
2

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

Output
3

Difficulty: HARD
Tags: Constructive algorithms

Sorting

Implementation

Dynamic programming

Data structures
Skill types: Dynamic programming

Sorting

Data structures

Starter code:

Solutions:
import io
import os
from collections import Counter, defaultdict, deque
from bisect import bisect_right
inf = float('inf')

def lengthOfLIS(nums, mn, mx):
	mnVal = mn - -1
	mxVal = mx - len(nums)
	chain = [mnVal]
	for (i, x) in enumerate(nums):
		v = x - i
		if mnVal > v or v > mxVal:
			continue
		newLen = bisect_right(chain, v)
		assert chain[newLen - 1] <= v
		if newLen == len(chain):
			chain.append(v)
		else:
			chain[newLen] = min(chain[newLen], v)
	return len(chain) - 1

def solve(N, K, A, B):
	ans = 0
	sB = [-1] + sorted(B) + [N]
	for (b1, b2) in zip(sB, sB[1:]):
		mn = -inf if b1 == -1 else A[b1]
		mx = inf if b2 == N else A[b2]
		nums = A[b1 + 1:b2]
		if mn >= mx:
			return -1
		if mx - mn - 1 < len(nums):
			return -1
		ans += len(nums) - lengthOfLIS(nums, mn, mx)
	if ans == inf:
		return -1
	return ans
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(N, K) = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
B = []
if K != 0:
	B = set((int(x) - 1 for x in input().split()))
print(solve(N, K, A, B))


import bisect

def solve(nums):
	n = len(nums)
	a = []
	nums = [nums[i] - i for i in range(n)]
	for i in range(n):
		if nums[i] < nums[0] or nums[i] > nums[n - 1]:
			continue
		k = bisect.bisect_right(a, nums[i])
		if k == len(a):
			a.append(nums[i])
		else:
			a[k] = nums[i]
	res = n - len(a)
	return res
(n, k) = input().split()
n = int(n)
k = int(k)
a = input().split()
for i in range(len(a)):
	a[i] = int(a[i])
if k == 0:
	b = []
else:
	b = list(map(int, input().split()))
a = [-10 ** 10] + a + [10 ** 10]
b = [0] + b + [n + 1]
res = 0
flag = True
(t, temp) = (b[0], a[0])
for i in b[1:]:
	if i - t > a[i] - temp:
		flag = False
		break
	res += solve(a[t:i + 1])
	(t, temp) = (i, a[i])
if flag:
	print(res)
else:
	print(-1)


import sys
from sys import stdin
import bisect

def LIS(lis, end):
	seq = []
	for c in lis:
		ind = bisect.bisect_right(seq, c)
		if ind == len(seq):
			seq.append(c)
		elif ind != 0:
			seq[ind] = c
	return bisect.bisect_right(seq, end)
tt = 1
for loop in range(tt):
	(n, k) = list(map(int, stdin.readline().split()))
	a = list(map(int, stdin.readline().split()))
	b = list(map(int, stdin.readline().split()))
	a = [float('-inf')] + a + [float('inf')]
	b = [0] + b + [n + 1]
	for i in range(n + 2):
		a[i] -= i
	for i in range(len(b) - 1):
		if a[b[i]] > a[b[i + 1]]:
			print(-1)
			return
	ans = n + 1
	for i in range(len(b) - 1):
		now = LIS(a[b[i]:b[i + 1]], a[b[i + 1]])
		ans -= now
	print(ans)


import bisect

def js(arr):
	n = len(arr)
	a = []
	arr = [int(arr[i]) - i for i in range(n)]
	for i in range(n):
		if int(arr[i]) < int(arr[0]) or int(arr[i]) > int(arr[n - 1]):
			continue
		k = bisect.bisect_right(a, int(arr[i]))
		if k == len(a):
			a.append(int(arr[i]))
		else:
			a[k] = int(arr[i])
	ans = n - len(a)
	return ans
(n, k) = input().split(' ')
n = int(n)
k = int(k)
ar = input().split(' ')
if k == 0:
	b = []
else:
	b = input().split(' ')
pd = True
b = [0] + b + [n + 1]
ar = [int(-1 * pow(10, 10))] + ar + [int(pow(10, 10))]
ans = 0
(h, j) = (int(b[0]), int(ar[0]))
for zc in b[1:]:
	zc = int(zc)
	if zc - h > int(ar[zc]) - j:
		pd = False
		break
	ans += js(ar[h:zc + 1])
	(h, j) = (zc, int(ar[zc]))
if pd:
	print(ans)
else:
	print(-1)


import bisect
(n, k) = map(int, input().split())
a = list(map(int, input().split()))

def work(number):
	a = []
	n = len(number)
	number = [number[i] - i for i in range(0, n)]
	for i in range(0, n):
		if number[i] < number[0] or number[i] > number[n - 1]:
			continue
		kk = bisect.bisect_right(a, number[i])
		if kk == len(a):
			a.append(number[i])
		else:
			a[kk] = number[i]
	nn = n - len(a)
	return nn
if k == 0:
	b = []
else:
	b = list(map(int, input().split()))
a = [-10 ** 10] + a + [10 ** 10]
b = [0] + b + [n + 1]
ans = 0
jud = True
(cut, number) = (b[0], a[0])
for c in b[1:]:
	if c - cut > a[c] - number:
		jud = False
		break
	ans += work(a[cut:c + 1])
	(cut, number) = (c, a[c])
if jud:
	print(ans)
else:
	print(-1)


import bisect

def lenSeq(num):
	n = len(num)
	a = []
	num = [num[i] - i for i in range(n)]
	for i in range(n):
		if num[i] < num[0] or num[i] > num[n - 1]:
			continue
		k = bisect.bisect_right(a, num[i])
		if k == len(a):
			a.append(num[i])
		else:
			a[k] = num[i]
	ans = n - len(a)
	return ans

def solver():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	if k == 0:
		b = []
	else:
		b = list(map(int, input().split()))
	a = [-10 ** 10] + a + [10 ** 10]
	b = [0] + b + [n + 1]
	ans = 0
	ok = True
	(cnt, num) = (b[0], a[0])
	for c in b[1:]:
		if c - cnt > a[c] - num:
			ok = False
			break
		ans += lenSeq(a[cnt:c + 1])
		(cnt, num) = (c, a[c])
	if ok:
		print(ans)
	else:
		print(-1)
solver()


def upper_bound(arr, target, l, r):
	i = l
	j = r
	mid = j
	while i < j:
		mid = (i + j) // 2
		if target >= arr[mid]:
			i = mid + 1
		else:
			j = mid
	return j
(x, y) = map(int, input().split())
a = [-10 ** 9] + list(map(int, input().split()))
a.append(10 ** 9)
b = [0]
if y != 0:
	b += list(map(int, input().split()))
b.append(x + 1)
b.sort()
d = []
for i in range(5 * 10 ** 5 + 100):
	d.append(0)

def count(l, r):
	global a, d
	len = 1
	d[len] = a[l]
	n = l + 1
	m = r + 1
	for i in range(n, m):
		if a[i] >= d[len]:
			len += 1
			d[len] = a[i]
		else:
			j = upper_bound(d, a[i], 1, len + 1)
			if j != 1:
				d[j] = a[i]
	pos = upper_bound(d, a[i], 1, len + 1) - 1
	return r - l + 1 - pos
flag = 1
if y > 1:
	for i in range(1, y):
		if a[b[i + 1]] - a[b[i]] < b[i + 1] - b[i]:
			flag = 0
			break
sum = 0
for i in range(1, x + 1):
	a[i] -= i
if flag == 0:
	print(-1)
else:
	for i in range(1, y + 2):
		sum += count(b[i - 1], b[i])
	print(sum)


import bisect

def ack(m, n):
	if m == 0:
		return n + 1
	elif m == 2:
		return 2 * (n + 1) + 1
	elif m == 1:
		return n + 2
	elif n == 0:
		return 5
	else:
		op = 5
		for i in range(0, n):
			op = op * 2 + 3
		return op

def mat(shuzu):
	n = len(shuzu)
	a = []
	shuzu = [shuzu[i] - i for i in range(n)]
	for i in range(n):
		kl = n - 1
		if shuzu[i] < shuzu[0] or shuzu[i] > shuzu[kl]:
			continue
		k = bisect.bisect_right(a, shuzu[i])
		if k == len(a):
			a.append(shuzu[i])
		else:
			a[k] = shuzu[i]
	res = n - len(a)
	return res
(n, m) = map(int, input().split())
opion1 = list(map(int, input().split()))
if m == 0:
	opion2 = []
else:
	opion2 = list(map(int, input().split()))
opion1 = [-10 ** 10] + opion1 + [10 ** 10]
opion2 = [0] + opion2 + [n + 1]
sum = 0
xuanze = 1
num = opion1[0]
fuhao = opion2[0]
for i in opion2[1:]:
	if i - fuhao > opion1[i] - num:
		xuanze = 0
		break
		for j in range(9):
			k = j * 9
	sum = sum + mat(opion1[fuhao:i + 1])
	num = opion1[i]
	fuhao = i
if xuanze:
	print(sum)
else:
	print(-1)


from bisect import bisect_right
(n, m) = map(int, input().split())
tp = 4557430888798830399
t = 0
a = [-tp] + [ai - i for (i, ai) in enumerate(map(int, input().split()))] + [tp]
b = [0] + (list(map(int, input().split())) if m else list()) + [n + 1]
for j in range(m + 1):
	s = b[j]
	r = b[j + 1]
	lst = list()
	for ai in a[s + 1:r]:
		if a[s] <= ai <= a[r]:
			tm = bisect_right(lst, ai)
			if tm == len(lst):
				lst.append(ai)
			else:
				lst[tm] = ai
	if a[r] < a[s]:
		print('-1')
		exit()
	t += r - s - 1 - len(lst)
print(t)


from bisect import bisect_right
INF = 4557430888798830399
(n, k) = map(int, input().split())
a = [-INF] + [ai - i for (i, ai) in enumerate(map(int, input().split()))] + [INF]
b = [0] + (list(map(int, input().split())) if k else list()) + [n + 1]
result = 0
for j in range(k + 1):
	left = b[j]
	right = b[j + 1]
	if a[right] < a[left]:
		print('-1')
		exit()
	nums = list()
	for ai in a[left + 1:right]:
		if a[left] <= ai <= a[right]:
			pos = bisect_right(nums, ai)
			if pos == len(nums):
				nums.append(ai)
			else:
				nums[pos] = ai
	result += right - left - 1 - len(nums)
print(result)


import sys, os, io
I = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, k) = map(int, I().split())
a = list(map(int, I().split()))
b = [0] + (list(map(int, I().split())) if k else []) + [n + 1]
a = [int(-10000000000.0)] + [a[i] - i - 1 for i in range(n)] + [int(10000000000.0)]
ans = 0
for bi in range(1, len(b)):
	(l, r) = (b[bi - 1], b[bi])
	if a[l] > a[r]:
		print(-1)
		break
	s = [-10000000000.0]
	dd = 1
	for x in a[l + 1:r]:
		if a[l] <= x <= a[r]:
			while dd <= len(s):
				dd *= 2
			(i, d) = (0, dd)
			while d:
				ii = i + d
				if ii < len(s):
					if s[ii] <= x:
						i = ii
				d //= 2
			i += 1
			if i < len(s):
				s[i] = x
			else:
				s.append(x)
	ans += r - l - len(s)
else:
	print(ans)


import bisect

def find(x, y, a):
	s = []
	for i in a:
		if x <= i and i <= y:
			j = bisect.bisect_right(s, i)
			if j == len(s):
				s.append(i)
			else:
				s[j] = i
	return len(s)
line = input().split()
n = int(line[0])
m = int(line[1])
line1 = list(map(int, input().split()))
for i in range(len(line1)):
	line1[i] -= i
line2 = []
if m != 0:
	line2 = list(map(int, input().split()))
line1 = [float('-inf')] + line1 + [float('inf')]
line2 = [0] + line2 + [n + 1]
ans = 0
for i in range(1, len(line2)):
	if line1[line2[i]] < line1[line2[i - 1]]:
		print('-1')
		break
	s = find(line1[line2[i - 1]], line1[line2[i]], line1[line2[i - 1] + 1:line2[i]])
	ans += line2[i] - line2[i - 1] - 1 - s
else:
	print(ans)


from bisect import bisect_right
inf = 4557430888798830399
(n, k) = map(int, input().split())
a = [-inf] + [ai - i for (i, ai) in enumerate(map(int, input().split()))] + [inf]
b = [0] + (list(map(int, input().split())) if k else list()) + [n + 1]
ans = 0
for j in range(k + 1):
	l = b[j]
	r = b[j + 1]
	if a[r] < a[l]:
		print('-1')
		exit()
	li = list()
	for ai in a[l + 1:r]:
		if a[l] <= ai <= a[r]:
			pos = bisect_right(li, ai)
			if pos == len(li):
				li.append(ai)
			else:
				li[pos] = ai
	ans += r - l - 1 - len(li)
print(ans)


import bisect

def solve(m1, m2, arr):
	st = []
	for c in arr:
		if m1 <= c <= m2:
			j = bisect.bisect_right(st, c)
			if j == len(st):
				st.append(c)
			else:
				st[j] = c
	return len(st)
(n, k) = map(int, input().split())
arrA = list(map(int, input().split()))
for (i, c) in enumerate(arrA):
	arrA[i] -= i
arrB = []
if k:
	arrB = list(map(int, input().split()))
arrA = [float('-inf')] + arrA + [float('inf')]
arrB = [0] + arrB + [n + 1]
ans = 0
for i in range(1, len(arrB)):
	if arrA[arrB[i]] < arrA[arrB[i - 1]]:
		print('-1')
		break
	ans += arrB[i] - arrB[i - 1] - 1 - solve(arrA[arrB[i - 1]], arrA[arrB[i]], arrA[arrB[i - 1] + 1:arrB[i]])
else:
	print(ans)


import sys
from copy import *
from bisect import *

def eprint(*args):
	print(*args, file=sys.stderr)
zz = 1
if zz:
	input = sys.stdin.readline
else:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('all.txt', 'w')
di = [[-1, 0], [1, 0], [0, 1], [0, -1]]

def string(s):
	return ''.join(s)

def fori(n):
	return [fi() for i in range(n)]

def inc(d, c, x=1):
	d[c] = d[c] + x if c in d else x

def bo(i):
	return ord(i) - ord('A')

def li():
	return [int(xx) for xx in input().split()]

def fli():
	return [float(x) for x in input().split()]

def comp(a, b):
	if a > b:
		return 2
	return 2 if a == b else 0

def gi():
	return [xx for xx in input().split()]

def cil(n, m):
	return n // m + int(n % m > 0)

def fi():
	return int(input())

def pro(a):
	return reduce(lambda a, b: a * b, a)

def swap(a, i, j):
	(a[i], a[j]) = (a[j], a[i])

def si():
	return list(input().rstrip())

def mi():
	return map(int, input().split())

def gh():
	sys.stdout.flush()

def isvalid(i, j, n, m):
	return 0 <= i < n and 0 <= j < m

def bo(i):
	return ord(i) - ord('a')

def graph(n, m):
	for i in range(m):
		(x, y) = mi()
		a[x].append(y)
		a[y].append(x)
t = 1
while t > 0:
	t -= 1
	(n, k) = mi()
	a = li()
	b = [n + 1]
	if k:
		b = li()
		b.append(n + 1)
	j = ans = p = pin = 0
	r = []
	for i in range(n):
		a[i] -= i
	prev = -10 ** 18
	for i in range(n):
		if i == b[j] - 1:
			y = bisect_right(r, a[i])
			ans += p - y
			if a[i] < prev:
				print(-1)
				exit(0)
			prev = a[i]
			pin = i + 1
			p = 0
			j += 1
			r = []
		else:
			if a[i] < prev:
				ans += 1
				continue
			y = bisect_right(r, a[i])
			if y == len(r):
				r.append(a[i])
			else:
				r[y] = min(r[y], a[i])
			p += 1
	ans += p - len(r)
	print(ans)


import sys
max_int = 1000000007
min_int = -max_int
(n, k) = map(int, sys.stdin.readline().split())
a = [min_int] + list(map(int, sys.stdin.readline().split())) + [max_int * 2]
for i in range(n + 2):
	a[i] = a[i] - i
if k:
	b = list(map(int, sys.stdin.readline().split()))
	b.sort()
else:
	b = []
diaps = []
l = 0
for bb in b:
	diaps.append((l, bb))
	l = bb
diaps.append((l, n + 1))
out = 0
for (l, r) in diaps:
	if a[r] < a[l]:
		out = -1
		break
	if r - l > 1:
		sl = []
		for i in range(l + 1, r):
			if a[r] >= a[i] >= a[l]:
				if not sl:
					sl.append(a[i])
				else:
					ll = -1
					rr = len(sl)
					while rr - ll > 1:
						m = (rr + ll) // 2
						if sl[m] > a[i]:
							rr = m
						else:
							ll = m
					if rr == len(sl):
						sl.append(a[i])
					else:
						sl[rr] = a[i]
		out += r - l - len(sl) - 1
print(out)


import sys, math
import io, os
data = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
from itertools import permutations, combinations

def mdata():
	return list(map(int, data().split()))

def outl(var):
	sys.stdout.write(' '.join(map(str, var)) + '\n')

def out(var):
	sys.stdout.write(str(var) + '\n')
INF = float('inf')
mod = int(1000000000.0) + 7

def LongestIncreasingSubsequenceLength(A, s, e):
	tailTable = [A[s] - s]
	for i in range(s + 1, e):
		if A[s] - s <= A[i] - i <= A[e] - e:
			ind = br(tailTable, A[i] - i)
			if ind == len(tailTable):
				tailTable.append(A[i] - i)
			else:
				tailTable[ind] = min(tailTable[ind], A[i] - i)
	return len(tailTable) - 1
(n, k) = mdata()
a = [-INF] + mdata() + [INF]
b = [0]
if k:
	b += sorted(mdata())
b += [n + 1]
for i in range(k + 1):
	if a[b[i + 1]] - a[b[i]] < b[i + 1] - b[i]:
		out(-1)
		exit()
ans = 0
for i in range(k + 1):
	ans += b[i + 1] - b[i] - 1 - LongestIncreasingSubsequenceLength(a, b[i], b[i + 1])
out(ans)


from sys import stdin, stdout

def make_it_increasing(n, k, a_a, b_a):
	res = 0
	a_a.insert(0, -10 ** 10)
	a_a.append(10 ** 20)
	b_a.insert(0, 0)
	b_a.append(len(a_a) - 1)
	for i in range(1, len(b_a)):
		l = b_a[i - 1]
		r = b_a[i]
		lv = a_a[l]
		rv = a_a[r]
		if r - l > rv - lv:
			return -1
		lst = []
		inc = 0
		for j in range(l + 1, r):
			inc += 1
			a_a[j] -= inc
			if a_a[j] < lv or a_a[j] > rv - (r - l):
				res += 1
				continue
			lst.append(a_a[j])
		res += len(lst) - lil(lst)
	return res

def lil(lst):
	tail = []
	for i in range(len(lst)):
		v = lst[i]
		l = 0
		h = len(tail) - 1
		if h == -1 or v >= tail[h]:
			tail.append(v)
			continue
		while l < h:
			m = (l + h) // 2
			if v >= tail[m]:
				l = m + 1
			else:
				h = m
		tail[l] = v
	return len(tail)
(n, k) = map(int, stdin.readline().split())
a_a = list(map(int, stdin.readline().split()))
b_a = []
if k > 0:
	b_a = list(map(int, stdin.readline().split()))
r = make_it_increasing(n, k, a_a, b_a)
stdout.write(str(r))


import sys
import bisect

def LIS(s, ed):
	lis = []
	for c in s:
		ind = bisect.bisect_right(lis, c)
		if ind == len(lis):
			lis.append(c)
		elif ind != 0:
			lis[ind] = c
	return bisect.bisect_right(lis, ed)
t = 1
while t:
	t -= 1
	(n, k) = map(int, input().split(' '))
	a = list(map(int, input().split(' ')))
	b = []
	if k:
		b = list(map(int, input().split(' ')))
	a = [float('-inf')] + a + [float('inf')]
	b = [0] + b + [n + 1]
	for i in range(n + 2):
		a[i] -= i
	lb = len(b)
	for i in range(lb - 1):
		if a[b[i]] > a[b[i + 1]]:
			print(-1)
			sys.exit()
	ans = n + 1
	for i in range(lb - 1):
		ans -= LIS(a[b[i]:b[i + 1]], a[b[i + 1]])
	print(ans)


maxn = int(500000.0 + 7)
aa = [0 for i in range(maxn)]
bb = [0 for i in range(maxn)]
dd = [0 for i in range(maxn)]

def check(m):
	for i in range(2, m + 1):
		if aa[bb[i]] < aa[bb[i - 1]]:
			return False
	return True

def upper_bound(l, r, x):
	while l < r:
		m = l + r >> 1
		if x >= dd[m]:
			l = m + 1
		else:
			r = m - 1
	return r + 1 if x >= dd[r] else r

def solve(l, r):
	n = 1
	dd[n] = aa[l]
	for i in range(l + 1, r + 1):
		if aa[i] >= dd[n]:
			n += 1
			dd[n] = aa[i]
		else:
			p = upper_bound(1, n, aa[i])
			if p != 1:
				dd[p] = aa[i]
	pos = upper_bound(1, n, aa[r]) - 1
	return r - l + 1 - pos
INF = 1061109567
(n, m) = map(int, input().split())
if n:
	c = list(map(int, input().split()))
	for i in range(n):
		aa[i + 1] = c[i]
		aa[i + 1] -= i + 1
aa[0] = -INF
aa[n + 1] = INF
bb[0] = 0
bb[m + 1] = n + 1
if m:
	c = list(map(int, input().split()))
	for i in range(m):
		bb[i + 1] = c[i]
if not check(m):
	print(-1)
else:
	ans = 0
	for i in range(1, m + 2):
		ans += solve(bb[i - 1], bb[i])
	print(ans)


import bisect

def solve(num):
	n = len(num)
	a = []
	num = [num[i] - i for i in range(n)]
	for i in range(n):
		if num[i] < num[0] or num[i] > num[n - 1]:
			continue
		k = bisect.bisect_right(a, num[i])
		if k == len(a):
			a.append(num[i])
		else:
			a[k] = num[i]
	sum = n - len(a)
	return sum
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
if k == 0:
	b = []
else:
	b = list(map(int, input().split()))
a = [-10 ** 10] + a + [10 ** 10]
b = [0] + b + [n + 1]
sum = 0
flag = 1
cnt = b[0]
num = a[0]
for c in b[1:]:
	if c - cnt > a[c] - num:
		flag = 0
		break
	sum += solve(a[cnt:c + 1])
	cnt = c
	num = a[c]
if flag:
	print(sum)
else:
	print(-1)


import bisect

def mat(arr):
	n = len(arr)
	a = []
	arr = [arr[i] - i for i in range(n)]
	for i in range(n):
		if arr[i] < arr[0] or arr[i] > arr[n - 1]:
			continue
		k = bisect.bisect_right(a, arr[i])
		if k == len(a):
			a.append(arr[i])
		else:
			a[k] = arr[i]
	res = n - len(a)
	return res
(n, m) = map(int, input().split())
num1 = list(map(int, input().split()))
if m == 0:
	num2 = []
else:
	num2 = list(map(int, input().split()))
num1 = [-10 ** 10] + num1 + [10 ** 10]
num2 = [0] + num2 + [n + 1]
sum = 0
ddd = 1
num = num1[0]
tmp = num2[0]
for i in num2[1:]:
	if i - tmp > num1[i] - num:
		ddd = 0
		break
	sum += mat(num1[tmp:i + 1])
	num = num1[i]
	tmp = i
if ddd:
	print(sum)
else:
	print(-1)


import sys, bisect
input = sys.stdin.readline

def LIS(A, end):
	sub = []
	for a in A:
		idx = bisect.bisect(sub, a)
		if idx == len(sub):
			sub.append(a)
		elif idx:
			sub[idx] = a
	return bisect.bisect(sub, end)
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a = [float('-inf')] + a + [float('inf')]
b = [0] + b + [n + 1]
for i in range(n + 2):
	a[i] -= i
for i in range(k + 1):
	if a[b[i]] > a[b[i + 1]]:
		print(-1)
		sys.exit()
ans = n + 1
for i in range(k + 1):
	cur = LIS(a[b[i]:b[i + 1]], a[b[i + 1]])
	ans -= cur
print(ans)


from bisect import bisect_right
from sys import stdin
input = stdin.readline

def solve():
	(n, k) = map(int, input().split())
	a = [float('-inf')] + list(map(int, input().split())) + [float('inf')]
	b = []
	if k != 0:
		b = [0] + list(map(int, input().split())) + [n + 1]
	else:
		b = [0, n + 1]
	res = n - k
	for (l, r) in zip(b, b[1:]):
		if a[r] - a[l] < r - l:
			print(-1)
			return
		lis = []
		left = a[l] - l
		right = a[r] - r
		for cur in range(l + 1, r):
			now = a[cur] - cur
			if left <= now <= right:
				pos = bisect_right(lis, now)
				if pos == len(lis):
					lis.append(now)
				else:
					lis[pos] = now
		res -= len(lis)
	print(res)
solve()


import bisect
P = input().split()
(n, k) = map(int, P)
a = list(map(int, input().split()))
y = 0
s = 90
H = 0
did = 1
if y < s:
	if k != 0:
		b = list(map(int, input().split()))
	else:
		b = []
a = [-10 ** 10] + a + [10 ** 10]
b = [0] + b + [n + 1]
C = b[0]
num = a[0]

def Over(num):
	n = len(num)
	a = []
	num = [num[i] - i for i in range(n)]
	for i in range(n):
		if num[i] < num[0] or num[i] > num[n - 1]:
			continue
		k = bisect.bisect_right(a, num[i])
		if k == len(a):
			a.append(num[i])
		else:
			a[k] = num[i]
	H = n - len(a)
	return H
for c in b[1:]:
	jk = c - C
	if jk > a[c] - num:
		did = 0
		break
	H = H + Over(a[C:c + 1])
	(C, num) = (c, a[c])
if did:
	print(H)
else:
	print(-1)


from bisect import *
from collections import *
from math import gcd, ceil, sqrt, floor, inf
from heapq import *
from typing import List
from itertools import *
from operator import add, mul, sub, xor, truediv, floordiv
from functools import *
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

@lru_cache(None)
def fact(x, mod=0):
	if x < 2:
		return 1
	if not mod:
		return fact(x - 1) * x
	return fact(x - 1, mod) * x % mod

@lru_cache(None)
def per(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return fact(i) // fact(i - j)
	ans = 1
	for k in range(i - j + 1, i + 1):
		ans = ans * k % mod
	return ans

@lru_cache(None)
def com(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return per(i, j) // fact(j)
	return per(i, j) * inverse(fact(j), mod) % mod

def catalan(n):
	return com(2 * n, n) // (n + 1)

def linc(f, t, l, r):
	while l < r:
		mid = (l + r) // 2
		if t > f(mid):
			l = mid + 1
		else:
			r = mid
	return l

def rinc(f, t, l, r):
	while l < r:
		mid = (l + r + 1) // 2
		if t < f(mid):
			r = mid - 1
		else:
			l = mid
	return l

def ldec(f, t, l, r):
	while l < r:
		mid = (l + r) // 2
		if t < f(mid):
			l = mid + 1
		else:
			r = mid
	return l

def rdec(f, t, l, r):
	while l < r:
		mid = (l + r + 1) // 2
		if t > f(mid):
			r = mid - 1
		else:
			l = mid
	return l

def isprime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def binfun(x):
	c = 0
	for w in arr:
		c += ceil(w / x)
	return c

def lowbit(n):
	return n & -n

def inverse(a, m):
	a %= m
	if a <= 1:
		return a
	return (1 - inverse(m, a) * m) // a % m

class BIT:

	def __init__(self, arr):
		self.arr = arr
		self.n = len(arr) - 1

	def update(self, x, v):
		while x <= self.n:
			self.arr[x] += v
			x += x & -x

	def query(self, x):
		ans = 0
		while x:
			ans += self.arr[x]
			x &= x - 1
		return ans

class smt:

	def __init__(self, l, r, arr):
		self.l = l
		self.r = r
		self.value = (1 << 31) - 1 if l < r else arr[l]
		mid = (l + r) // 2
		if l < r:
			self.left = smt(l, mid, arr)
			self.right = smt(mid + 1, r, arr)
			self.value &= self.left.value & self.right.value

	def setvalue(self, x, val):
		if self.l == self.r:
			self.value = val
			return
		mid = (self.l + self.r) // 2
		if x <= mid:
			self.left.setvalue(x, val)
		else:
			self.right.setvalue(x, val)
		self.value = self.left.value & self.right.value

	def ask(self, l, r):
		if l <= self.l and r >= self.r:
			return self.value
		val = (1 << 31) - 1
		mid = (self.l + self.r) // 2
		if l <= mid:
			val &= self.left.ask(l, r)
		if r > mid:
			val &= self.right.ask(l, r)
		return val

class DSU:

	def __init__(self, n):
		self.c = [-1] * n

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def find(self, x):
		if self.c[x] < 0:
			return x
		self.c[x] = self.find(self.c[x])
		return self.c[x]

	def union(self, u, v):
		(u, v) = (self.find(u), self.find(v))
		if u == v:
			return False
		if self.c[u] < self.c[v]:
			(u, v) = (v, u)
		self.c[u] += self.c[v]
		self.c[v] = u
		return True

	def size(self, x):
		return -self.c[self.find(x)]

class UFS:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.ranks = [0] * n

	def find(self, x):
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, u, v):
		(pu, pv) = (self.find(u), self.find(v))
		if pu == pv:
			return False
		if self.ranks[pu] >= self.ranks[pv]:
			self.parent[pv] = pu
			if self.ranks[pv] == self.ranks[pu]:
				self.ranks[pu] += 1
		else:
			self.parent[pu] = pv

def Prime(n):
	c = 0
	prime = []
	flag = [0] * (n + 1)
	for i in range(2, n + 1):
		if not flag[i]:
			prime.append(i)
			c += 1
		for j in range(c):
			if i * prime[j] > n:
				break
			flag[i * prime[j]] = prime[j]
			if i % prime[j] == 0:
				break
	return prime

def dij(s, graph):
	d = {}
	d[s] = 0
	heap = [(0, s)]
	seen = set()
	while heap:
		(dis, u) = heappop(heap)
		if u in seen:
			continue
		for v in graph[u]:
			if v not in d or d[v] > d[u] + graph[u][v]:
				d[v] = d[u] + graph[u][v]
				heappush(heap, (d[v], v))
	return d
(n, k) = RLL()
a = RLL()
a = [a[i] - i for i in range(n)]
if k:
	b = RLL()
	l = len(b)
	ans = 0
	b = [b[i] - 1 for i in range(l)]
	for i in range(1, l):
		if a[b[i - 1]] > a[b[i]]:
			print(-1)
			exit()
	for i in range(1, l):
		res = []
		stack = []
		for j in range(b[i - 1] + 1, b[i]):
			if a[b[i - 1]] <= a[j] <= a[b[i]]:
				res.append(a[j])
		for x in res:
			ind = bisect_right(stack, x)
			if ind == len(stack):
				stack.append(x)
			else:
				stack[ind] = x
		ans += b[i] - b[i - 1] - 1 - len(stack)
	res = []
	stack = []
	for j in range(b[0]):
		if a[j] <= a[b[0]]:
			res.append(a[j])
	for x in res:
		ind = bisect_right(stack, x)
		if ind == len(stack):
			stack.append(x)
		else:
			stack[ind] = x
	ans += b[0] - len(stack)
	res = []
	stack = []
	for j in range(b[-1] + 1, n):
		if a[j] >= a[b[-1]]:
			res.append(a[j])
	for x in res:
		ind = bisect_right(stack, x)
		if ind == len(stack):
			stack.append(x)
		else:
			stack[ind] = x
	ans += n - 1 - b[-1] - len(stack)
	print(ans)
else:
	stack = []
	for i in a:
		ind = bisect_right(stack, i)
		if ind == len(stack):
			stack.append(i)
		else:
			stack[ind] = i
	print(n - len(stack))


from bisect import bisect_right as br
inf = float('inf')
(n, k) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
b = []
if k > 0:
	b = [int(x) for x in input().split()]
blocked = [False for _ in range(n)]
for x in b:
	blocked[x - 1] = True
a = [-inf] + a + [inf]
blocked = [True] + blocked + [True]
a2 = [0 for _ in range(n + 2)]
for i in range(n + 2):
	a2[i] = a[i] - i
segments = []
prevBlocked = 0
for i in range(n + 2):
	if blocked[i] and i > 0:
		segments.append(a2[prevBlocked:i + 1])
		prevBlocked = i

def minChangeToMakeNonDecreasing(segment):
	minVal = [0]
	if segment[0] > segment[-1]:
		return inf
	minVal.append(segment[0])
	for i in range(1, len(segment) - 1):
		l = br(minVal, segment[i])
		if l == len(minVal):
			minVal.append(inf)
		if minVal[l] == segment[i]:
			if l + 1 == len(minVal):
				minVal.append(0)
			minVal[l + 1] = segment[i]
		elif l != 1:
			minVal[l] = segment[i]
	maxNondecreasingSubseqLen = br(minVal, segment[-1])
	return len(segment) - maxNondecreasingSubseqLen
ans = 0
for segment in segments:
	ans += minChangeToMakeNonDecreasing(segment)
if ans == inf:
	ans = -1
print(ans)


import sys, io, os
BUFSIZE = 8192

class FastIO(io.IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = io.BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(io.IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from bisect import bisect_right
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
A = [a - i for (i, a) in enumerate(A)]
if K:
	B = list(map(int, input().split()))
else:
	B = []
B = [0] + B + [N + 1]
A = [-(1 << 60)] + A + [1 << 60]
ans = 0
for (b1, b2) in zip(B, B[1:]):
	if A[b1] > A[b2]:
		print(-1)
		exit()
	C = A[b1:b2 + 1]
	L = [A[0]]
	for a in C[1:-1]:
		if C[0] <= a <= C[-1]:
			if a >= L[-1]:
				L.append(a)
			else:
				L[bisect_right(L, a)] = a
	l = len(L) + 1
	ans += len(C) - l
print(ans)


import bisect
INF = 4557430888798830399
(pa, pb) = map(int, input().split())
m = [-INF] + [mi - i for (i, mi) in enumerate(map(int, input().split()))] + [INF]
n = [0] + (list(map(int, input().split())) if pb else list()) + [pa + 1]
temp = 0
for j in range(pb + 1):
	k = n[j]
	q = n[j + 1]
	if m[q] < m[k]:
		print('-1')
		exit()
	lis = list()
	for mi in m[k + 1:q]:
		if m[k] <= mi <= m[q]:
			pos = bisect.bisect(lis, mi)
			if pos == len(lis):
				lis.append(mi)
			else:
				lis[pos] = mi
	temp += q - k - 1 - len(lis)
print(temp)


from bisect import bisect_right
INF = 4557430888798830399
(n, k) = map(int, input().split())
m = [-INF] + [ai - i for (i, ai) in enumerate(map(int, input().split()))] + [INF]
t = [0] + (list(map(int, input().split())) if k else list()) + [n + 1]
ans = 0
for j in range(k + 1):
	l = t[j]
	r = t[j + 1]
	if m[r] < m[l]:
		print('-1')
		exit()
	lis = list()
	for ai in m[l + 1:r]:
		if m[l] <= ai <= m[r]:
			pos = bisect_right(lis, ai)
			if pos == len(lis):
				lis.append(ai)
			else:
				lis[pos] = ai
	ans += r - l - 1 - len(lis)
print(ans)


import sys

def upper_bound(nums, target, p):
	(low, high) = (0, p - 1)
	pos = p
	while low < high:
		mid = (low + high) // 2
		if nums[mid] <= target:
			low = mid + 1
		else:
			high = mid
			pos = high
	if nums[low] > target:
		pos = low
	return pos
(n, k) = map(int, input().split())
alist = list(map(int, input().split()))
if k != 0:
	dlist = list(map(int, input().split()))
clist = [0 for i in range(500500)]
blist = [0 for i in range(500500)]
for i in range(k):
	a = dlist[i]
	blist[a] = 1
alist.insert(0, -sys.maxsize)
alist.append(sys.maxsize)
blist[0] = blist[n + 1] = 1
i = 0
ans = 0
while i <= n:
	j = i + 1
	while blist[j] != 1:
		j += 1
	if alist[j] < alist[i] + j - i:
		break
	top = 0
	clist[top] = 0
	top += 1
	for k in range(i + 1, j):
		if alist[k] - alist[i] - k + i < 0:
			alist[k] = sys.maxsize
		else:
			alist[k] = alist[k] - alist[i] - k + i
		if alist[k] >= clist[top - 1]:
			clist[top] = alist[k]
			top += 1
		else:
			pos = upper_bound(clist, alist[k], top)
			clist[pos] = alist[k]
	pos = upper_bound(clist, alist[j] - alist[i] - j + i, top)
	ans += j - i - pos
	i = j
if i <= n:
	print(-1)
else:
	print(ans)


import sys
from array import array
from bisect import bisect_right

def input():
	return sys.stdin.buffer.readline().decode('utf-8')
(n, k) = map(int, input().split())
a = [-2 * 10 ** 9] + list(map(int, input().split())) + [2 * 10 ** 9]
if k:
	b = [0] + list(map(int, input().split())) + [n + 1]
else:
	b = [0, n + 1]
if not all((a[j] - a[i] >= j - i for (i, j) in zip(b, b[1:]))):
	print(-1)
	exit()
ans = 0
for (l, r) in zip(b, b[1:]):
	lis = [a[l] - l]
	(lb, ub) = (a[l] - l, a[r] - r)
	for i in range(l + 1, r):
		if not lb <= a[i] - i <= ub:
			pass
		else:
			j = bisect_right(lis, a[i] - i)
			if j >= len(lis):
				lis.append(a[i] - i)
			else:
				lis[j] = a[i] - i
	ans += r - l - len(lis)
print(ans)


a = []
b = []
inf = 1061109567
import bisect

def solve(num):
	n = len(num)
	a = []
	num = [num[i] - i for i in range(n)]
	for i in range(n):
		if num[i] < num[0] or num[i] > num[n - 1]:
			continue
		k = bisect.bisect_right(a, num[i])
		if k == len(a):
			a.append(num[i])
		else:
			a[k] = num[i]
	ans = n - len(a)
	return ans
s = input()
s = [x for x in s.split()]
n = int(s[0])
k = int(s[1])
s1 = input()
s1 = [x for x in s1.split()]
if k != 0:
	s2 = input()
	s2 = [x for x in s2.split()]
else:
	s2 = []
for i in range(1, n + 1):
	a.append(int(s1[i - 1]))
if k != 0:
	for i in range(1, k + 1):
		b.append(int(s2[i - 1]))
a = [-inf] + a + [inf]
b = [0] + b + [n + 1]
ans = 0
sign = True
(cnt, num) = (b[0], a[0])
for c in b[1:]:
	if c - cnt > a[c] - num:
		sign = False
		break
	ans += solve(a[cnt:c + 1])
	(cnt, num) = (c, a[c])
if sign:
	print(ans)
else:
	print(-1)


import bisect
INF = 4557430888798830399
(n, k) = map(int, input().split())
a = [-INF] + [ai - i for (i, ai) in enumerate(map(int, input().split()))] + [INF]
b = [0] + (list(map(int, input().split())) if k else list()) + [n + 1]
ans = 0
for j in range(k + 1):
	l = b[j]
	r = b[j + 1]
	if a[r] < a[l]:
		print('-1')
		exit()
	lis = list()
	for ai in a[l + 1:r]:
		if a[l] <= ai <= a[r]:
			pos = bisect.bisect(lis, ai)
			if pos == len(lis):
				lis.append(ai)
			else:
				lis[pos] = ai
	lenn = len(lis)
	ans += r - l - 1 - lenn
print(ans)


import bisect

def calculate(num):
	aa = []
	bb = []
	n = len(num)
	num = [num[i] - i for i in range(0, n)]
	for i in range(0, n):
		if num[i] > num[n - 1] or num[i] < num[0]:
			continue
		kk = bisect.bisect_right(aa, num[i])
		if kk != len(aa):
			aa[kk] = num[i]
		else:
			aa.append(num[i])
	return n - len(aa)
outt = 1
(n, k) = map(int, input().split())
a1 = []
a1 = list(map(int, input().split()))
if k != 0:
	a2 = list(map(int, input().split()))
else:
	a2 = []
a1 = [-10 ** 10] + a1 + [10 ** 10]
a2 = [0] + a2 + [n + 1]
aa1 = a1[0]
aa2 = a2[0]
outt = 0
flag = True
for j in a2[1:]:
	if j + aa1 > a1[j] + aa2:
		flag = False
		break
	outt = outt + calculate(a1[aa2:j + 1])
	aa1 = a1[j]
	aa2 = j
if flag == False:
	print(-1)
else:
	print(outt)


from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush, heappop
import math
from collections import *
from functools import reduce, cmp_to_key, lru_cache
import sys
input = sys.stdin.readline
M = mod = 998244353

def factors(n):
	return sorted(set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0))))

def inv_mod(n):
	return pow(n, mod - 2, mod)

def li():
	return [int(i) for i in input().rstrip('\n').split()]

def st():
	return input().rstrip('\n')

def val():
	return int(input().rstrip('\n'))

def li2():
	return [i for i in input().rstrip('\n')]

def li3():
	return [int(i) for i in input().rstrip('\n')]

def give(i, j, mi, ma):
	l1 = []
	for k in range(i, j + 1):
		if mi <= l[k] <= ma:
			ind = br(l1, l[k])
			if ind == len(l1):
				l1.append(l[k])
			else:
				l1[ind] = l[k]
	return j - i - len(l1) + 1
(n, k) = li()
l = [0] + li()
if k:
	b = li()
else:
	b = []
for i in range(1, k):
	if l[b[i]] - l[b[i - 1]] < b[i] - b[i - 1] or l[b[i]] < l[b[i - 1]]:
		print(-1)
		return
for i in range(n + 1):
	l[i] -= i
if k:
	ans = give(1, b[0] - 1, -float('inf'), l[b[0]])
	ans += give(b[-1] + 1, n, l[b[-1]], float('inf'))
	for i in range(1, k):
		ans += give(b[i - 1], b[i], l[b[i - 1]], l[b[i]])
else:
	ans = give(1, n, -float('inf'), float('inf'))
print(ans)


import sys, os, io
input = sys.stdin.readline
from bisect import bisect_right
(N, K) = map(int, input().split())
A = [-float('inf')] + list(map(int, input().split())) + [float('inf')]
if K:
	B = [0] + list(map(int, input().split())) + [N + 1]
else:
	B = [0, N + 1]
ans = N - K
for k in range(K + 1):
	(left, right) = (B[k], B[k + 1])
	if A[left] - left > A[right] - right:
		print(-1)
		break
	lis = []
	for i in range(left + 1, right):
		if not A[left] - left <= A[i] - i <= A[right] - right:
			continue
		ind = bisect_right(lis, A[i] - i)
		if ind == len(lis):
			lis.append(A[i] - i)
		else:
			lis[ind] = A[i] - i
	ans -= len(lis)
else:
	print(ans)


import sys

def upper_bound(nums, key, p):
	(left, right) = (0, p - 1)
	pos = p
	while left < right:
		mid = (left + right) // 2
		if nums[mid] <= key:
			left = mid + 1
		else:
			right = mid
			pos = right
	if nums[left] > key:
		pos = left
	return pos
(n, k) = map(int, input().split())
alist = list(map(int, input().split()))
if k != 0:
	dlist = list(map(int, input().split()))
listc = [0 for i in range(500010)]
listb = [0 for i in range(500010)]
for i in range(k):
	a = int(dlist[i])
	listb[a] = 1
alist.insert(0, -sys.maxsize)
alist.append(sys.maxsize)
listb[0] = listb[n + 1] = 1
i = 0
ans = 0
while i <= n:
	j = i + 1
	while listb[j] != 1:
		j += 1
	if alist[j] < alist[i] + j - i:
		break
	top = 0
	listc[top] = 0
	top += 1
	for k in range(i + 1, j):
		if alist[k] - alist[i] - k + i < 0:
			alist[k] = sys.maxsize
		else:
			alist[k] = alist[k] - alist[i] - k + i
		if alist[k] >= listc[top - 1]:
			listc[top] = alist[k]
			top += 1
		else:
			pos = upper_bound(listc, alist[k], top)
			listc[pos] = alist[k]
	pos = upper_bound(listc, alist[j] - alist[i] - j + i, top)
	ans += j - i - pos
	i = j
if i <= n:
	print(-1)
else:
	print(ans)


def check(a, b, m):
	for i in range(2, m):
		if a[b[i]] < a[b[i - 1]]:
			return False
	return True

def upper_bound(d, x):
	l = 1
	r = len(d) - 1
	while l <= r:
		mid = l + r >> 1
		if x >= d[mid]:
			l = mid + 1
		else:
			r = mid - 1
	return l

def solve(l, r):
	loc = 1
	d = list()
	d.append(0)
	d.append(a[l])
	for i in range(l + 1, r + 1):
		if a[i] >= d[loc]:
			loc += 1
			d.append(a[i])
		else:
			j = upper_bound(d, a[i])
			if j != 1:
				d[j] = a[i]
	pos = upper_bound(d, a[r]) - 1
	return r - l + 1 - pos
(x, y) = map(int, input().split())
b = list()
a = list(map(int, input().split()))
a.insert(0, -1061109567)
a.append(1061109567)
LEN = len(a)
for i in range(1, LEN - 1):
	a[i] -= i
if y:
	b = list(map(int, input().split()))
	b.insert(0, 0)
	b.append(x + 1)
ans = 0
if not check(a, b, y + 1):
	print('-1')
else:
	if y == 0:
		b.append(0)
		b.append(len(a) - 1)
	for i in range(1, y + 2):
		ans += solve(b[i - 1], b[i])
	print(ans)


import bisect
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
if k == 0:
	b = []
else:
	b = list(map(int, input().split()))
a = [-10 ** 10] + a + [10 ** 10]
b = [0] + b + [n + 1]
res = 0
ok = 1
(cnt, num) = (b[0], a[0])

def solve(num):
	n = len(num)
	a = []
	num = [num[i] - i for i in range(n)]
	for i in range(n):
		if num[i] < num[0] or num[i] > num[n - 1]:
			continue
		k = bisect.bisect_right(a, num[i])
		if k != len(a):
			a[k] = num[i]
		else:
			a.append(num[i])
	res = n - len(a)
	return res
for t in b[1:]:
	if t - cnt > a[t] - num:
		ok = 0
		break
	res += solve(a[cnt:t + 1])
	(cnt, num) = (t, a[t])
if ok:
	print(res)
else:
	print(-1)


from bisect import bisect_right
f = 4557430888798830399
(n, k) = map(int, input().split())
array = [-f] + [ai - i for (i, ai) in enumerate(map(int, input().split()))] + [f]
line = [0] + (list(map(int, input().split())) if k else list()) + [n + 1]
result = 0
for j in range(k + 1):
	mark = line[j]
	r = line[j + 1]
	if array[r] < array[mark]:
		print('-1')
		exit()
	li = list()
	for ai in array[mark + 1:r]:
		if array[mark] <= ai <= array[r]:
			pos = bisect_right(li, ai)
			if pos == len(li):
				li.append(ai)
			else:
				li[pos] = ai
	result += r - mark - 1 - len(li)
print(result)


def find(increase, search):
	left = 0
	right = len(increase) - 1
	while left <= right:
		middle = (left + right) // 2
		if increase[middle] <= search:
			left = middle + 1
		else:
			right = middle - 1
	return left
s = input()
s = s.split(' ')
alength = int(s[0])
blength = int(s[1])
s = input()
s = s.split(' ')
alist = [-10 ** 9]
for i in range(alength):
	alist.append(int(s[i]))
blist = []
if blength > 0:
	s = input()
	s = s.split(' ')
	for i in range(blength):
		blist.append(int(s[i]))
blist.append(alength + 1)
canIncrease = True
for i in range(1, blength):
	tempA = blist[i - 1]
	tempB = blist[i]
	if alist[tempA] + tempB - tempA > alist[tempB]:
		canIncrease = False
		break
	tempA = tempB
if canIncrease == False:
	print(-1)
else:
	blist.insert(0, 0)
	result = 0
	alist.append(10 ** 9)
	for i in range(alength + 1):
		alist[i] = alist[i] - i
	final = 0
	for i in range(1, blength + 2):
		tempA = blist[i - 1]
		tempB = blist[i]
		increase = [0, alist[tempA]]
		lengthIncrease = 1
		for j in range(tempA + 1, tempB + 1):
			if alist[j] >= increase[-1]:
				increase.append(alist[j])
				lengthIncrease += 1
			else:
				index = find(increase, alist[j])
				if index != 1:
					increase[index] = alist[j]
		final = find(increase, alist[tempB]) - 1
		final = tempB - tempA + 1 - final
		result += final
	print(result)


import bisect

def fun(num):
	n = len(num)
	a = []
	num = [num[i] - i for i in range(n)]
	for i in range(n):
		if num[i] < num[0] or num[i] > num[n - 1]:
			continue
		k = bisect.bisect_right(a, num[i])
		if k != len(a):
			a[k] = num[i]
		else:
			a.append(num[i])
	result = n - len(a)
	return result
(n, k) = map(int, input().split())
a = []
b = []
s = input().split()
for it in s:
	a.append(int(it))
if k != 0:
	s = input().split()
	for it in s:
		b.append(int(it))
a = [-10 ** 10] + a + [10 ** 10]
b = [0] + b + [n + 1]
result = 0
flag = 1
cnt = b[0]
num = a[0]
for j in b[1:]:
	if j - cnt > a[j] - num:
		flag = 0
		break
	result += fun(a[cnt:j + 1])
	cnt = j
	num = a[j]
if flag != 1:
	print(-1)
else:
	print(result)


mod = 1000000007
eps = 10 ** (-9)

def main():
	import sys
	from bisect import bisect_left
	input = sys.stdin.buffer.readline

	def len_LIS(seg):
		n = len(seg)
		l = seg[0]
		r = seg[-1]
		A = seg[1:-1]
		LIS = [l]
		for a in A:
			if not l <= a <= r:
				continue
			j = bisect_left(LIS, a + 1)
			if j == len(LIS):
				LIS.append(a)
			else:
				LIS[j] = a
		return len(LIS) - 1
	(N, K) = map(int, input().split())
	A = [-10 ** 10] + list(map(int, input().split())) + [10 ** 10]
	for i in range(N + 2):
		A[i] -= i
	if K:
		B = [0] + list(map(int, input().split())) + [N + 1]
	else:
		B = [0, N + 1]
	ans = 0
	for i in range(K + 1):
		l = B[i]
		r = B[i + 1]
		if A[r] - A[l] < 0:
			print(-1)
			exit()
		ans += r - l - 1 - len_LIS(A[l:r + 1])
	print(ans)
main()


import bisect

def solve(T):
	n = len(T)
	a = []
	T = [T[i] - i for i in range(n)]
	for i in range(n):
		if T[i] < T[0] or T[i] > T[n - 1]:
			continue
		k = bisect.bisect_right(a, T[i])
		if k == len(a):
			a.append(T[i])
		else:
			a[k] = T[i]
	g = n - len(a)
	return g
(p, q) = map(int, input().split())
l = list(map(int, input().split()))
if q == 0:
	b = []
else:
	b = list(map(int, input().split()))
l = [-10 ** 10] + l + [10 ** 10]
b = [0] + b + [p + 1]
sum = 0
ok = True
(z, num) = (b[0], l[0])
for c in b[1:]:
	if c - z > l[c] - num:
		ok = False
		break
	sum += solve(l[z:c + 1])
	(z, num) = (c, l[c])
if ok:
	print(sum)
else:
	print(-1)


def upper_bound(nums, target):
	if not nums:
		return 0
	(low, high) = (0, len(nums) - 1)
	pos = len(nums)
	while low < high:
		mid = (low + high) // 2
		if nums[mid] <= target:
			low = mid + 1
		else:
			high = mid
			pos = high
	if nums[low] > target:
		pos = low
	return pos
INF = 4557430888798830399
(n, k) = map(int, input().split())
a = [-INF] + [ai - i for (i, ai) in enumerate(map(int, input().split()))] + [INF]
b = [0] + (list(map(int, input().split())) if k else list()) + [n + 1]
ans = 0
for j in range(k + 1):
	l = b[j]
	r = b[j + 1]
	if a[r] < a[l]:
		print('-1')
		exit()
	lis = list()
	for ai in a[l + 1:r]:
		if a[l] <= ai <= a[r]:
			pos = upper_bound(lis, ai)
			if pos == len(lis):
				lis.append(ai)
			else:
				lis[pos] = ai
	ans += r - l - 1 - len(lis)
print(ans)


def sep():
	return map(int, input().strip().split(' '))

def lis():
	return list(sep())

def N():
	return int(input())
import bisect

def solve():

	def LIS(lis, end):
		seq = []
		for c in lis:
			ind = bisect.bisect_right(seq, c)
			if ind == len(seq):
				seq.append(c)
			elif ind != 0:
				seq[ind] = c
		return bisect.bisect_right(seq, end)
	(n, m) = sep()
	a = [-9999999999999] + lis() + [9999999999999999]
	if m:
		b = lis()
	else:
		b = []
	b.sort()
	b = [0] + b + [n + 1]
	for i in range(n + 2):
		a[i] -= i
	for i in range(m + 1):
		if a[b[i]] > a[b[i + 1]]:
			print(-1)
			return
	ans = n + 1
	for i in range(m + 1):
		ans -= LIS(a[b[i]:b[i + 1]], a[b[i + 1]])
	print(ans)

def testcase():
	for _ in range(N()):
		solve()
solve()


import bisect

def solve(num):
	n = len(num)
	temp = []
	num = [num[i] - i for i in range(n)]
	for i in range(n):
		if num[i] < num[0] or num[i] > num[n - 1]:
			continue
		k = bisect.bisect_right(temp, num[i])
		if k == len(temp):
			temp.append(num[i])
		else:
			temp[k] = num[i]
	ans = n - len(temp)
	return ans

def upper_bound(nums, target):
	(low, high) = (0, len(nums) - 1)
	pos = len(nums)
	while low < high:
		mid = (low + high) / 2
		if nums[mid] <= target:
			low = mid + 1
		else:
			high = mid
			pos = high
	if nums[low] > target:
		pos = low
	return pos
s = input()
s = [x for x in s.split()]
n = int(s[0])
m = int(s[1])
inf = 1061109567
a = []
b = []
s1 = input()
s1 = [x for x in s1.split()]
if m != 0:
	s2 = input()
	s2 = [x for x in s2.split()]
else:
	s2 = []
for i in range(1, n + 1):
	a.append(int(s1[i - 1]))
if m != 0:
	for i in range(1, m + 1):
		b.append(int(s2[i - 1]))
a = [-inf] + a + [inf]
b = [0] + b + [n + 1]
ans = 0
flag = True
cnt = b[0]
num = a[0]
for c in b[1:]:
	if c - cnt > a[c] - num:
		flag = False
		break
	ans = ans + solve(a[cnt:c + 1])
	cnt = c
	num = a[c]
if flag:
	print(ans)
else:
	print(-1)


import bisect

def funm(arr):
	n = len(arr)
	a = list()
	arr = [arr[i] - i for i in range(n)]
	for i in range(n):
		if arr[i] < arr[0] or arr[i] > arr[n - 1]:
			continue
		k = bisect.bisect_right(a, arr[i])
		if k == len(a):
			a.append(arr[i])
		else:
			a[k] = arr[i]
	ans = n - len(a)
	return ans

def fun(aa):
	n = len(aa)
	for i in range(n):
		aa = aa[i] - i
	for i in range(n):
		if aa[i] < aa[0] or aa[i] > aa[n - 1]:
			continue
(n, m) = map(int, input().split())
num1 = list(map(int, input().split()))
if m == 0:
	num2 = list()
else:
	num2 = list(map(int, input().split()))
num1 = [-10 ** 10] + num1 + [10 ** 10]
num2 = [0] + num2 + [n + 1]
sum = 0
flag = 1
num = num1[0]
tmp = num2[0]
z = 0
for i in range(0, n):
	if i - sum > num1[i]:
		z = 2 ** 3
	else:
		z = sum
for i in num2[1:]:
	if i - tmp > num1[i] - num:
		flag = 0
		break
	sum += funm(num1[tmp:i + 1])
	num = num1[i]
	tmp = i
if flag:
	print(sum)
else:
	print(-1)


import bisect

def TSort():
	one = False
	zero = False
	flag = True
	for i in range(0, n):
		if i < n - 1:
			if a[i + 1] < a[i]:
				flag = False
		if b[i] == 0:
			one = True
		else:
			zero = True
	if flag or (one and zero):
		print('Yes')
	else:
		print('No')

def snynb(arr):
	n = len(arr)
	a = []
	arr = [arr[i] - i for i in range(n)]
	for i in range(n):
		if arr[i] < arr[0] or arr[i] > arr[n - 1]:
			continue
		k = bisect.bisect_right(a, arr[i])
		if k == len(a):
			a.append(arr[i])
		else:
			a[k] = arr[i]
	x = n - len(a)
	return x

def okk(mid):
	global n, shuzu, k, m
	m = 0
	zonghe = 0
	cnt = 0
	for i in range(n):
		if zonghe + shuzu[i] >= mid:
			if zonghe > m:
				m = zonghe
			zonghe = shuzu[i]
			cnt = cnt + 1
		else:
			zonghe = zonghe + shuzu[i]
	return cnt < k
(n, m) = map(int, input().split())
num1 = list(map(int, input().split()))
if m == 0:
	num2 = []
else:
	num2 = list(map(int, input().split()))
num1 = [-10 ** 10] + num1 + [10 ** 10]
num2 = [0] + num2 + [n + 1]
sum = 0
sny = 1
num = num1[0]
t = num2[0]
for i in num2[1:]:
	if i - t > num1[i] - num:
		sny = 0
		break
	sum += snynb(num1[t:i + 1])
	num = num1[i]
	t = i
if sny:
	print(sum)
else:
	print(-1)


from bisect import bisect_right
(n, k) = map(int, input().split())
a = [-2000000000.0] + list(map(int, input().split())) + [2000000000.0]
b = [0, n + 1]
if k:
	b = [0] + list(map(int, input().split())) + [n + 1]
k += 2
n += 2
for i in range(n):
	a[i] -= i
ans = 0
for i in range(1, k):
	if a[b[i]] - a[b[i - 1]] < 0:
		print(-1)
		exit()
	r = b[i]
	l = b[i - 1]
	cur = []
	for j in range(l + 1, r):
		if a[l] <= a[j] <= a[r]:
			ind = bisect_right(cur, a[j])
			if ind == len(cur):
				cur.append(a[j])
			else:
				cur[ind] = a[j]
	ans += r - l - 1 - len(cur)
print(ans)


import bisect

def stablesort(s, l6):
	l3 = []
	l4 = [0]
	for i in range(len(s)):
		if l6[0] == -1:
			if s[i] <= l[l6[1]]:
				k = bisect.bisect(l3, s[i])
				if len(l3) == 0 or l3[-1] <= s[i]:
					l3.append(s[i])
					l4.append(l4[-1] + 1)
				else:
					l3[k] = s[i]
		elif l[l6[1]] >= s[i] >= l[l6[0]]:
			k = bisect.bisect(l3, s[i])
			if len(l3) == 0 or l3[-1] <= s[i]:
				l3.append(s[i])
				l4.append(l4[-1] + 1)
			else:
				l3[k] = s[i]
	return len(l3)
(n, k) = map(int, input().split())
l = list(map(int, input().split())) + [float('inf')]
l2 = []
tt = 0
for i in range(n):
	l[i] -= i
if k > 0:
	kk = list(map(int, input().split()))
if k > 0:
	for i in range(k - 1):
		if l[kk[i] - 1] > l[kk[i + 1] - 1]:
			tt = 1
			break
	if tt == 1:
		print(-1)
		exit(0)
	else:
		ans = 0
		w = 0
		c = 0
		l5 = []
		for i in range(0, k):
			l1 = []
			for j in range(c, kk[i] - 1):
				l1.append(l[j])
			if len(l1) > 0:
				l2.append(l1)
				l5.append([c - 1, kk[i] - 1])
			w = l[kk[i] - 1]
			c = kk[i]
		l1 = []
		for i in range(c, n):
			l1.append(l[i])
		if len(l1) > 0:
			l2.append(l1)
			l5.append([c - 1, n])
else:
	l3 = []
	for i in range(n):
		k = bisect.bisect(l3, l[i])
		if len(l3) == 0 or l3[-1] <= l[i]:
			l3.append(l[i])
		else:
			l3[k] = l[i]
	print(n - len(l3))
	exit(0)
if len(l2) > 0:
	for i in range(len(l2)):
		c = stablesort(l2[i], l5[i])
		ans += c
	print(n - (ans + k))
else:
	print(n - k)


import bisect

def solve(numss):
	n = len(numss)
	a = []
	numss = [numss[i] - i for i in range(n)]
	for i in range(n):
		if numss[i] < numss[0] or numss[i] > numss[n - 1]:
			continue
		k = bisect.bisect_right(a, numss[i])
		if k == len(a):
			a.append(numss[i])
		else:
			a[k] = numss[i]
	res = n - len(a)
	return res

def main():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	if k == 0:
		b = []
	else:
		b = list(map(int, input().split()))
	a = [-10 ** 10] + a + [10 ** 10]
	b = [0] + b + [n + 1]
	res = 0
	ok = True
	(t, tp) = (b[0], a[0])
	for i in b[1:]:
		if i - t > a[i] - tp:
			ok = False
			break
		res += solve(a[t:i + 1])
		(t, tp) = (i, a[i])
	if ok:
		print(res)
	else:
		print(-1)
main()


maxn = int(500000.0 + 7)
a = []
b = []
d = []
for i in range(maxn):
	a.append(0)
	b.append(0)
	d.append(0)

def upper(l, r, x):
	while l < r:
		m = l + r >> 1
		if x >= d[m]:
			l = m + 1
		else:
			r = m - 1
	return r + 1 if x >= d[r] else r

def solve(l, r):
	n = 1
	d[n] = a[l]
	for i in range(l + 1, r + 1):
		if a[i] >= d[n]:
			n += 1
			d[n] = a[i]
		else:
			p = upper(1, n, a[i])
			if p != 1:
				d[p] = a[i]
	pos = upper(1, n, a[r]) - 1
	return r - l + 1 - pos
INF = 1061109567
(n, m) = map(int, input().split())
if n:
	c = list(map(int, input().split()))
	for i in range(n):
		a[i + 1] = c[i]
		a[i + 1] -= i + 1
a[0] = -INF
a[n + 1] = INF
b[0] = 0
b[m + 1] = n + 1
if m:
	c = list(map(int, input().split()))
	for i in range(m):
		b[i + 1] = c[i]

def check(m):
	for i in range(2, m + 1):
		if a[b[i]] < a[b[i - 1]]:
			return False
	return True
if not check(m):
	print(-1)
else:
	ans = 0
	for i in range(1, m + 2):
		ans += solve(b[i - 1], b[i])
	print(ans)


from math import inf
from bisect import bisect_right
(n, k) = map(int, input().split())
data = list(map(int, input().split()))
a = [-inf]
b = [0]
for elem in data:
	a.append(elem)
a.append(inf)
for i in range(n + 2):
	a[i] -= i
if k != 0:
	data2 = list(map(int, input().split()))
else:
	data2 = []
for elem in data2:
	b.append(elem)
b.append(n + 1)
ans = 0
c = True
for i in range(k + 1):
	left = b[i]
	right = b[i + 1]
	if a[left] > a[right]:
		print('-1')
		c = False
		break
	used = []
	for j in range(left + 1, right):
		if a[left] <= a[j] <= a[right]:
			position = bisect_right(used, a[j])
			if position == len(used):
				used.append(a[j])
			else:
				used[position] = a[j]
	ans += right - left - 1 - len(used)
if c:
	print(ans)


from bisect import bisect_right

def lwis(array):
	lwis_array = [array[0]]
	for i in range(1, len(array) - 1):
		a = array[i]
		if a >= lwis_array[-1]:
			lwis_array.append(a)
		else:
			lwis_array[bisect_right(lwis_array, a)] = a
	a = array[-1]
	if a >= lwis_array[-1]:
		return len(lwis_array) + 1
	else:
		return bisect_right(lwis_array, a) + 1

def solve(l, r):
	tmp = a[l:r]
	val = a[l]
	length = r - l
	res = 0
	li = []
	for i in range(length):
		if i == length - 1 and tmp[i] - val - i < 0:
			res += INF
		if tmp[i] - val - i < 0:
			pass
		else:
			li.append(tmp[i] - val - i)
	if res >= INF:
		return INF
	res += length - lwis(li)
	return res
import sys
input = sys.stdin.buffer.readline
INF = 10 ** 12
(n, k) = map(int, input().split())
a = [-INF] + list(map(int, input().split())) + [INF]
if k != 0:
	tmp = list(map(int, input().split()))
else:
	tmp = []
b = [0]
for i in tmp:
	b.append(i)
b.append(n + 1)
ans = 0
for i in range(len(b) - 1):
	ans += solve(b[i], b[i + 1] + 1)
if ans >= INF:
	print(-1)
else:
	print(ans)


from sys import stdin
(n, k) = [int(x) for x in stdin.readline().split()]
a = [int(x) for x in stdin.readline().split()]
for x in range(n):
	a[x] -= x
if k == 0:
	b = set()
else:
	b = set([int(y) - 1 for y in stdin.readline().split()])

def bS(a, n):
	l = 0
	r = len(a) - 1
	while l <= r:
		m = (l + r) // 2
		if a[m] <= n:
			l = m + 1
		else:
			r = m - 1
	return r
table = {0: a[0]}
l = 1
low = -float('inf')
cool = True
bList = sorted(list(b))
for x in bList:
	if a[x] < low:
		cool = False
		break
	else:
		low = a[x]
if not cool:
	print(-1)
else:
	if not bList:
		b2 = [0] + bList + [n]
		weird = False
	elif bList[0] != 0:
		b2 = [0] + bList + [n]
		weird = False
	else:
		b2 = bList + [n]
		weird = True
	a.append(float('inf'))

	def lis(low, high, left, right, a):
		if left == right:
			return 0
		l = 1
		c = left
		while a[c] < low or a[c] > high:
			c += 1
			if c == right:
				return 0
		table = {0: a[c]}
		for ind in range(c + 1, right):
			x = a[ind]
			if x < low or x > high:
				continue
			if x < table[0]:
				table[0] = x
			elif x >= table[l - 1]:
				table[l] = x
				l += 1
			else:
				tI = bS(table, x)
				table[tI + 1] = x
		return l
	l = 0
	for x in range(len(b2) - 1):
		if x == 0:
			if weird:
				l += lis(a[0], a[b2[1]], 0, b2[1], a)
			else:
				l += lis(-float('inf'), a[b2[1]], 0, b2[1], a)
		elif x == len(b2) - 2:
			l += lis(a[b2[-2]], float('inf'), b2[-2], n, a)
		else:
			l += lis(a[b2[x]], a[b2[x + 1]], b2[x], b2[x + 1], a)
	print(n - l)


import sys
input = sys.stdin.readline
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
b = []
if k:
	b = list(map(int, input().split()))
for i in range(n):
	a[i] -= i
prev = -1
ans = 0
for j in range(k + 1):
	if j < k:
		val = b[j] - 1
		if j and a[prev] > a[val]:
			print(-1)
			quit()
	else:
		val = n
	if val - prev > 1:
		path = [0] * (val - prev - 1)
		arr = [0] * (val - prev)
		found = 0
		for i in range(val - prev - 1):
			if val < n and a[i + prev + 1] > a[val]:
				continue
			elif prev + 1 and a[prev] > a[i + prev + 1]:
				continue
			l = 1
			h = found
			while h >= l:
				m = (l + h + 1) // 2
				if a[arr[m] + prev + 1] <= a[i + prev + 1]:
					l = m + 1
				else:
					h = m - 1
			path[i] = arr[l - 1]
			arr[l] = i
			if l > found:
				found = l
		ans += found
	prev = val
print(n - k - ans)


import bisect

def mat(array):
	length = len(array)
	a = []
	array = [array[i] - i for i in range(length)]
	for j in range(length):
		if array[j] < array[0] or array[j] > array[length - 1]:
			continue
		k = bisect.bisect_right(a, array[j])
		if k == len(a):
			a.append(array[j])
		else:
			a[k] = array[j]
	res = length - len(a)
	return res
(n, m) = map(int, input().split())
x1 = list(map(int, input().split()))
if m == 0:
	x2 = []
else:
	x2 = list(map(int, input().split()))
x1 = [-10 ** 10] + x1 + [10 ** 10]
x2 = [0] + x2 + [n + 1]
sum = 0
Isans = True
num = x1[0]
temp = x2[0]
for i in x2[1:]:
	if i - temp > x1[i] - num:
		Isans = False
		break
	sum += mat(x1[temp:i + 1])
	num = x1[i]
	temp = i
if Isans:
	print(sum)
else:
	print(-1)


import bisect
import sys
(n, k) = map(int, input().split())
a = [0] + list(map(int, input().split()))
if k > 0:
	b = [0] + list(map(int, input().split()))
for i in range(1, k):
	if a[b[i]] >= a[b[i + 1]] or a[b[i + 1]] - a[b[i]] < b[i + 1] - b[i]:
		print(-1)
		sys.exit(0)
inf = -10 ** 9
a = [inf + 1] + [a[i] - i for i in range(1, n + 1)] + [-inf]
b = [0] + [b[i] for i in range(1, k + 1)] + [n + 1]
n += 2
k += 2

def lis(a):
	c = [inf * 2] + [-inf * 2] * (n + 5)
	for i in range(len(a)):
		u = bisect.bisect_right(c, a[i])
		c[u] = a[i]
	for i in reversed(range(len(a) + 1)):
		if c[i] != -inf * 2:
			return i
for i in range(k - 1):
	for x in range(b[i] + 1, b[i + 1]):
		if not a[b[i]] <= a[x] <= a[b[i + 1]]:
			a[x] = inf
			inf -= 1
print(n - lis(a))


import sys, math, itertools
from collections import Counter, deque, defaultdict
from bisect import bisect_left, bisect_right
mod = 10 ** 9 + 7
INF = float('inf')

def inp():
	return int(sys.stdin.readline())

def inpl():
	return list(map(int, sys.stdin.readline().split()))
(n, k) = inpl()
a = inpl()
if k != 0:
	b = inpl()
pre = 0
bad = False
for i in range(k - 1):
	lind = b[i] - 1
	rind = b[i + 1] - 1
	l = a[lind]
	r = a[rind]
	if r - l < rind - lind:
		bad = True
if bad:
	print(-1)
	quit()
l = []
r = []
dv = []
if k == 0:
	l = [-INF]
	r = [INF]
	dv = [a]
else:
	for (_, i) in enumerate(b):
		dv.append(a[pre:i - 1])
		if pre == 0:
			l.append(-INF)
		else:
			l.append(a[pre - 1])
		r.append(a[i - 1])
		pre = i
	dv.append(a[pre:])
	l.append(a[pre - 1])
	r.append(INF)
res = 0
for i in range(k + 1):
	li = []
	L = l[i] + 1
	R = r[i] - 1
	ln = len(dv[i])
	for (j, x) in enumerate(dv[i]):
		if L + j <= x <= R - ln + j + 1:
			li.append(x - j)
	dp = [INF] * len(li)
	for (i, x) in enumerate(li):
		ind = bisect_right(dp, x)
		dp[ind] = x
	ans = len(li)
	for (i, x) in enumerate(dp):
		if x == INF:
			ans = i
			break
	res += ln - ans
print(res)


import sys
import math
from bisect import bisect_right

def II():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def MI():
	return map(int, sys.stdin.readline().split())

def SI():
	return sys.stdin.readline().strip()
(n, k) = MI()
a = LI()
a = [float('-inf')] + a + [float('inf')]
b = []
if k != 0:
	b = LI()
b = [0] + b + [n + 1]
ans = n - k
for i in range(k + 1):
	l = b[i]
	r = b[i + 1]
	if a[l] - l > a[r] - r:
		print(-1)
		exit(0)
	lis = []
	for j in range(l + 1, r):
		if not a[l] - l <= a[j] - j <= a[r] - r:
			continue
		ind = bisect_right(lis, a[j] - j)
		if ind == len(lis):
			lis.append(a[j] - j)
		else:
			lis[ind] = a[j] - j
	ans -= len(lis)
print(ans)


from bisect import bisect_right
INF = 10 ** 9 + 1
(n, k) = map(int, input().split())
a = [-INF] + [ai - i for (i, ai) in enumerate(map(int, input().split()))] + [INF]
b = [0] + (list(map(int, input().split())) if k else list()) + [n + 1]
ans = 0
for j in range(k + 1):
	l = b[j]
	r = b[j + 1]
	if a[r] < a[l]:
		print('-1')
		exit()
	lis = list()
	for ai in a[l + 1:r]:
		if a[l] <= ai <= a[r]:
			pos = bisect_right(lis, ai)
			if pos == len(lis):
				lis.append(ai)
			else:
				lis[pos] = ai
	ans += r - l - 1 - len(lis)
print(ans)


import bisect
(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
remain = []
if k > 0:
	remain = list(map(int, input().split()))
for i in range(n):
	arr[i] = arr[i] - i
remain = [0] + remain + [n + 1]
arr = [-2147483648] + arr + [2147483647]

def getremove(front, rear, minimum, maximum):
	if minimum > maximum:
		return -1
	sub = []
	output = 0
	for ele in arr[front:rear + 1]:
		if ele > maximum or ele < minimum:
			continue
		loc = bisect.bisect(sub, ele)
		if loc == len(sub):
			sub.append(ele)
		else:
			sub[loc] = ele
	return rear - front + 1 - len(sub)
ans = 0
for i in range(k + 1):
	temp = getremove(remain[i] + 1, remain[i + 1] - 1, arr[remain[i]], arr[remain[i + 1]])
	if temp >= 0:
		ans += temp
	else:
		ans = -1
		break
print(ans)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline()

def RL():
	return map(int, sys.stdin.readline().split())

def RLL():
	return list(map(int, sys.stdin.readline().split()))

def N():
	return int(input())

def print_list(l):
	print(' '.join(map(str, l)))
import bisect as bs
(n, k) = RL()
a = RLL()
b = RLL()
flag = True
for i in range(1, k):
	(x, y) = (b[i - 1], b[i])
	if a[y - 1] - a[x - 1] < y - x:
		flag = False
		break
if not flag:
	print(-1)
else:
	a = [a[i] - i for i in range(n)]
	j = 0
	d = [0] * (n + 1)
	e = 0
	s = 0
	for i in range(n):
		if s > 0 and a[i] < d[s - 1]:
			continue
		p = bs.bisect_right(d, a[i], s, e)
		d[p] = a[i]
		if j < k and i + 1 == b[j]:
			j += 1
			e = p + 1
			s = p + 1
		elif p == e:
			e += 1
	print(n - e)


import os, sys
from io import BytesIO, IOBase
from bisect import bisect_left as bl, bisect_right as br
INF = float('inf')

def cal(a, l, r):
	b = [a[i] - (i - l) for i in range(l, r + 1)]
	(dp, ind) = ([b[0]], [0])
	for i in range(1, r - l):
		x = br(dp, b[i])
		if x == len(dp):
			dp.append(b[i])
			ind.append(i)
		elif x:
			(dp[x], ind[x]) = (b[i], i)
	x = br(dp, b[-1])
	if not x:
		return INF
	return r - l - x

def main():
	(n, k) = map(int, input().split())
	a = [-INF] + list(map(int, input().split())) + [INF]
	b = [0] + list(map(int, input().split())) + [n + 1] if k else [0, n + 1]
	z = sum((cal(a, b[i], b[i + 1]) for i in range(k + 1)))
	print(-1 if z == INF else z)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import bisect
import collections
import copy
import functools
import heapq
import itertools
import math
import random
import re
import sys
import time
import string
sys.setrecursionlimit(99999)
(n, k) = map(int, input().split())
arrA = list(map(int, input().split()))
for (i, c) in enumerate(arrA):
	arrA[i] -= i
arrB = []
if k:
	arrB = list(map(int, input().split()))
arrA = [float('-inf')] + arrA + [float('inf')]
arrB = [0] + arrB + [n + 1]
ans = 0

def solve(m1, m2, arr):
	st = []
	for c in arr:
		if m1 <= c <= m2:
			j = bisect.bisect_right(st, c)
			if j == len(st):
				st.append(c)
			else:
				st[j] = c
	return len(st)
for i in range(1, len(arrB)):
	if arrA[arrB[i]] < arrA[arrB[i - 1]]:
		print('-1')
		break
	ans += arrB[i] - arrB[i - 1] - 1 - solve(arrA[arrB[i - 1]], arrA[arrB[i]], arrA[arrB[i - 1] + 1:arrB[i]])
else:
	print(ans)


import bisect
INF = 4557430888798830399
(n, k) = map(int, input().split())
a = [-INF] + [ai - i for (i, ai) in enumerate(map(int, input().split()))] + [INF]
b = [0] + (list(map(int, input().split())) if k else list()) + [n + 1]

def dsfa():
	m = 0

def gsdfa():
	c = 0
ans = 0
for j in range(k + 1):
	l = b[j]
	r = b[j + 1]
	if a[r] < a[l]:
		print('-1')
		exit()
	lis = list()
	for ai in a[l + 1:r]:
		if a[l] <= ai <= a[r]:
			pos = bisect.bisect(lis, ai)
			if pos == len(lis):
				lis.append(ai)
			else:
				lis[pos] = ai
	ans += r - l - 1 - len(lis)
print(ans)


import sys
sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.buffer.readline())

def MI():
	return map(int, sys.stdin.buffer.readline().split())

def LI():
	return list(map(int, sys.stdin.buffer.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def BI():
	return sys.stdin.buffer.readline().rstrip()

def SI():
	return sys.stdin.buffer.readline().rstrip().decode()
from bisect import bisect

def solve():
	ans = 0
	for (l, r) in zip(bb, bb[1:]):
		if aa[r] < aa[l]:
			return -1
		mn = aa[l]
		mx = aa[r]
		lis = [aa[l]]
		for i in range(l + 1, r):
			a = aa[i]
			if not mn <= a <= mx:
				continue
			j = bisect(lis, a)
			if j == len(lis):
				lis.append(a)
			elif j:
				lis[j] = a
		ans += r - l - len(lis)
	return ans
inf = 10 ** 10
(n, k) = MI()
aa = [-inf] + LI() + [inf]
bb = [0] + LI() + [n + 1] if k else [0, n + 1]
aa = [a - i for (i, a) in enumerate(aa)]
print(solve())