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;
}