Технокубок 2017 - Отборочный Раунд 2 |
---|
Закончено |
В крупной компании работают n сотрудников, каждый из которых имеет уникальный номер от 1 до n. Из них ровно один сотрудник является главным, его номер равен s. Также известно, что все сотрудники, кроме главного, имеют ровно одного непосредственного начальника.
Каждому из сотрудников было поручено подать информацию о том, сколько начальников у него есть (не только непосредственных). Под начальниками сотрудника понимается его непосредственный начальник, а также непосредственный начальник непосредственного начальника данного сотрудника, и так далее. Например, если в компании три сотрудника, первый из которых главный, у второго сотрудника непосредственный начальник — первый сотрудник, а у третьего сотрудника непосредственный начальник второй сотрудник, то у третьего сотрудника всего два начальника — один непосредственный и один не непосредственный. Главный сотрудник является начальником всех сотрудников, кроме самого себя.
Некоторые из сотрудников поторопились, ошиблись в подсчете и подали неверную информацию. Перед вами стоит задача определить минимально возможное число сотрудников, которые могли допустить ошибку при подаче информации.
В первой строке следует два целых положительных числа n и s (1 ≤ n ≤ 2·105, 1 ≤ s ≤ n) — количество сотрудников и номер главного сотрудника.
Во второй строке следует n целых чисел a1, a2, ..., an (0 ≤ ai ≤ n - 1), где ai равно количеству начальников (не обязательно непосредственных) у сотрудника i, о котором он сообщил при подаче информации.
Выведите минимально возможное число сотрудников, которые могли допустить ошибку при подаче информации.
3 2
2 0 2
1
5 3
1 0 0 4 1
2
В первом примере мог ошибиться, например, только первый сотрудник, в том случае, если:
Название |
---|