e-olymp
Yarışlar

2018 Всероссийская олимпиада школьников по информатике, Москва

Экспедиция

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

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

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

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

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

В первой строке находится целое число n (1n300 000) - количество кандидатов. В следующих n строках даны результаты опроса, i-я из этих строк содержит результат опроса i-го кандидата, целое число ai (ai = -1 или 1ain, aii).

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

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

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
4
2
4
2
1
Çıxış verilənləri #1
2
Giriş verilənləri #2
3
2
-1
2
Çıxış verilənləri #2
2
Mənbə 2018 Всероссийская олимпиада школьников по информатике, Региональный этап, день 2, Москва, 28 января 2019, Задача C