Экспедиция

Планируется отправить экспедицию к соседней звёздной системе. Были отобраны n кандидатов, пронумерованных от 1 до n, среди которых необходимо выбрать участников экспедиции. Организаторы хотят отправить в экспедицию как можно больше кандидатов.

Среди кандидатов был проведён опрос, в процессе которого каждый мог указать не более, чем одного из остальных кандидатов, с которым он не готов отправиться в экспедицию. Результатом опроса для i-го кандидата является целое число a_i, которое равно номеру кандидата, с которым i-й кандидат не готов отправиться в экспедицию, либо -1, если i-й кандидат готов отправиться в экспедицию в любом составе.

Теперь организаторы должны выбрать, кто из кандидатов отправится в экспедицию. Решено было выбрать участников экспедиции так, что если туда входит некоторый кандидат i, и a_i ≠ -1, то туда не входит кандидат a_i. Организаторы хотят выбрать максимальное количество участников экспедиции.

Требуется написать программу, которая по заданным результатам опроса кандидатов определяет максимальное количество кандидатов, которых можно отправить в экспедицию.

Входные данные

В первой строке входного файла INPUT.TXT находится целое число n − количество кандидатов (1 ⩽ n ⩽ 300 000).

В следующих n строках даны результаты опроса, i-я из этих строк содержит результат опроса i-го кандидата, целое число a_i (a_i = -1 или 1 ⩽ a_i ⩽ n, a_i ≠ i).

Выходные данные

В единственной строке выходного файла OUTPUT.TXT выведите одно целое число — максимальное количество кандидатов, которых можно отправить в экспедицию.

Примеры

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]