There are n workers in a company, each of them has a unique id from 1 to n. Exaclty one of them is a chief, his id is s. Each worker except the chief has exactly one immediate superior.

There was a request to each of the workers to tell how how many superiors (not only immediate). Worker's superiors are his immediate superior, the immediate superior of the his immediate superior, and so on. For example, if there are three workers in the company, from which the first is the chief, the second worker's immediate superior is the first, the third worker's immediate superior is the second, then the third worker has two superiors, one of them is immediate and one not immediate. The chief is a superior to all the workers except himself.

Some of the workers were in a hurry and made a mistake. You are to find the minimum number of workers that could make a mistake.


-----Input-----

The first line contains two positive integers n and s (1 ≤ n ≤ 2·10^5, 1 ≤ s ≤ n) — the number of workers and the id of the chief.

The second line contains n integers a_1, a_2, ..., a_{n} (0 ≤ a_{i} ≤ n - 1), where a_{i} is the number of superiors (not only immediate) the worker with id i reported about.


-----Output-----

Print the minimum number of workers that could make a mistake.


-----Examples-----
Input
3 2
2 0 2

Output
1

Input
5 3
1 0 0 4 1

Output
2



-----Note-----

In the first example it is possible that only the first worker made a mistake. Then:   the immediate superior of the first worker is the second worker,  the immediate superior of the third worker is the first worker,  the second worker is the chief.

Difficulty: interview

Starter code:

Solutions:
n,s = map(int,input().split())
A = list(map(int,input().split()))
if A[s-1] != 0:
    per = 1
    A[s-1] = 0
else:
    per = 0
A.sort()
maxs = max(A)
ans = [0] * (maxs + 1)
answer = maxs + 1
o = -1
for j in range(n):
    if A[j] == 0:
        o += 1
    
    if ans[A[j]] == 0:
        ans[A[j]] = 1
        answer -= 1
an = per + max(o, answer)

for j in range(n-2,-1,-1):
    
    for t in range(A[j+1]-1, A[j] -1,-1):
        if ans[t] == 0:
            answer -= 1
    
    an = min(an, per + max(answer,o+n - j - 1))
print(an)

""" This is a solution to the problem Subordinates on codeforces.com
    
    There is a DAG with n nodes, pointing towards the root, without further constraints. 
    Given: for each node, a number signifying the count of (direct and indirect) predecessors, and the ID of root s.
    Some of these counts might be wrong. Give the minimum amount of wrong counts.
    
    For details, see
    http://codeforces.com/problemset/problem/729/E
"""

#Idea: count = level of DAG. Check constraints: root has 0 predecessors, level 0 has only one count, each level to the last has be > 0

from sys import stdin

#lines = open("input.txt", 'r').readlines()
lines = stdin.readlines()

n, s = map(int, lines[0].split())
counts = list(map(int, lines[1].split()))
    
totalwrong = 0
if counts[s-1] > 0: # root has to be 0
    totalwrong += 1
    counts[s-1] = 0
     
maxlevel = max(counts)    
# count number of nodes on levels
levelcount = [0] * (max(counts) + 1)

for c in counts:
    levelcount[c] += 1
    
curwrong = levelcount[0] - 1 # only one root
levelcount[0] = 1
totalwrong += curwrong 

curlevel = 0
while curlevel <= maxlevel:
    lc = levelcount[curlevel]
    if lc == 0:         # a mistake
        if curwrong > 0: # still mistakes available, just use them to fill
            curwrong -= 1
            levelcount[curlevel] = 1
        else: # else fill from last level
            levelcount[maxlevel] -= 1
            levelcount[curlevel] = 1        
            totalwrong += 1
            while levelcount[maxlevel] == 0:
                maxlevel -= 1       # as levelcount[curlevel] = 1, this aborts at some point
    curlevel += 1
print(totalwrong)

f = lambda: map(int, input().split())
n, s = f()
c = [0] * n
t = list(f())
for i in t: c[i] += 1
k = t[s - 1]
c[k] -= 1
d = c[0]
c += [d]
d += k > 0
i, j = 1, n
while i < j:
    if c[i]: i += 1
    elif c[j]:
        c[j] -= 1
        i += 1
        d += j < n
    else: j -= 1
print(d)

[n, s] = [int(x) for x in input().split()]

a = [int(x) for x in input().split()]

mistakes = 0

mistakes += (a[s-1] is not 0)
a[s - 1] = 0

numSuperiors = [0]*(2*100000+100)

for superiors in a:
    numSuperiors[superiors] += 1

cachedMistakes = 0

while numSuperiors[0] != 1:
    cachedMistakes += 1
    numSuperiors[0] -= 1

rightIndex = len(numSuperiors) - 1
leftIndex = 0
while True:
    while True:
        if numSuperiors[leftIndex] == 0 and cachedMistakes != 0:
            numSuperiors[leftIndex] += 1
            cachedMistakes -= 1
            mistakes += 1
        if numSuperiors[leftIndex] == 0:
            break
        leftIndex += 1
    while numSuperiors[rightIndex] == 0:
        rightIndex -= 1
    if leftIndex >= rightIndex:
        break
    numSuperiors[rightIndex] -= 1
    cachedMistakes += 1

print(mistakes)

n, root = map(int, input().split())
a = list(map(int, input().split()))

def push(d, x, val):
    if x not in d:
        d[x] = 0
    d[x]+=val
    
    if d[x]==0:
        del d[x]
    
d = {}
for x in a:
    push(d, x, 1)

min_  =  0
root -=  1
inf   = 9999999

if a[root] != 0:
    min_+=1
    push(d, a[root], -1)
    push(d, 0, 1)
    
if 0 in d and d[0] > 1:
    add  = d[0] - 1
    min_+=add
    push(d, inf, add)
    d[0] = 1
    
S   = [[val, num] for val, num in sorted(d.items(), key = lambda x:x[0])] 
#print(min_, S)
cur = -1
i   =  0

while i < len(S):
    remain = S[i][0] - (cur+1)
    
    while remain > 0:
        val, num = S[-1]
        
        if val == S[i][0]:
            if val != inf:
                min_ += min(remain, num)
            break   
        else:
            add     = min(num, remain)
            remain -= add
            
            if val != inf:
                min_   += add
            
            if num == add:
                S.pop()
            else:    
                S[-1][1] -= add
        
    cur=S[i][0]
    i+=1
    
print(min_)