시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB205525.000%

문제

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

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

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

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

입력

В первой строке входных данных находится целое число n — количество кандидатов (1 ⩽ n ⩽ 300 000).

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

출력

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

서브태스크

번호배점제한
119

n ⩽ 20

210

a1 = −1

для i > 1 выполнено ai = i − 1

315

для всех i выполнено ai < i

413

1 ⩽ n ⩽ 2000

543

1 ⩽ n ⩽ 300 000

예제 입력 1

4
2
4
2
1

예제 출력 1

2

예제 입력 2

3
2
-1
2

예제 출력 2

2

채점 및 기타 정보

  • 예제는 채점하지 않는다.