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: interview

Starter code:

Solutions:
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)
        else:
            if 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 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)
# print(dv,l,r)
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)

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):
    # print(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]
    # print(j - i + 1, len(l1))
    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
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 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)