Задача E. Экспедиция

Автор:Центральная предметно-методическая комиссия   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

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

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

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

Формат входных данных

В первой строке входных данных находится целое число n  — количество кандидатов.

В следующих n строках даны результаты опроса, i-я из этих строк содержит результат опроса i-го кандидата, целое число ai.

Формат выходных данных

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

Ограничения

1 ≤ n ≤ 300 000

ai = −1 или 1 ≤ ai ≤ n, ai ≠ i

Описание подзадач и системы оценивания

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

Подзадача Баллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
119n ≤ 20полная
210a1 = −1, для i > 1 выполнено ai = i − 1первая ошибка
315для всех i выполнено ai < i2первая ошибка
4131 ≤ n ≤ 20001первая ошибка
5431 ≤ n ≤ 300 0001, 2, 3, 4первая ошибка

Примеры тестов

Стандартный вход Стандартный выход
1
4
2
4
2
1
2
2
3
2
-1
2
2

0.041s 0.007s 15