Codeforces Round #380 Div. 1 C. Subordinates(贪心)

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·105, 1 ≤ s ≤ n) — the number of workers and the id of the chief.

The second line contains n integers a1, a2, ..., an (0 ≤ ai ≤ n - 1), where ai 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.

题意：有n个工人，每个工人有一个顶头上司，每个工人的上司包括他的顶头上司和顶头上司的上司，n个工人中有一个dalao，dalao是所有人的上司，现在每个工人报一个数字表示他上司的数量，问最少有多少个工人是误报的，dalao是第s个工人。

分析：工人的阶层关系构成了一棵树，我们考虑枚举这棵树的高度h,如果当前工人的上司数量大于树的高度，那么他一定是误报了，如果还有其他的dalao那么一定也是误报了，还有一个明显的限制就是如果树的高度为h，那么1到h的结点必须至少都存在一个，把工人的上司数量排序后，扫一遍就可以了。

PS ： 注意如果给的点s不是dalao，那么我们可以直接把他改成dalao然后ans+1.

#include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<set>
#include<map>
#include<vector>
#include<cstring>
#include<stack>
#include<queue>
#define INF 0x3f3f3f3f
#define eps 1e-9
#define N 200005  
using namespace std;
int n,pre,ans,preli,root,cnt[N],f[N];
bool flag = false;
vector<int> q;
int main()
{
	scanf("%d%d",&n,&root);
	for(int i = 1;i <= n;i++)
	{
		scanf("%d",&cnt[i]);
		if(i == root && cnt[i]) 
		{
			flag = true;
			cnt[i] = 0;
		}
	}
	ans = INF;
	sort(cnt+1,cnt+1+n);
	for(int i = 1;i <= n;i++)
	{
		int temp = cnt[i];
		if(i != 1 && !temp) preli++;
		while(temp && !f[temp-1])
		{
			pre++;
			f[--temp] = 1;
		}
		if(cnt[i] && !f[cnt[i]-1])
		{
			pre++;
			f[cnt[i]-1] = 1;
		}
		f[cnt[i]]++;
		ans = min(ans,max(n-i+preli,pre));
	}
	cout<<ans+flag<<endl;
}