favorite We need a little bit of your help to keep things running, click on this banner to learn more

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


It is planned to send an expedition to a neighbouring star system. n candidates were selected, numbered from 1 to n, among whom it was necessary to select the expedition members. The organisers want to send as many candidates as possible to the expedition.

A survey was conducted among the candidates, during which everyone could indicate no more than one of the other candidates with whom he was not ready to go to expedition. The result of the survey for the i - th candidate is an integer ai, that equals to the number of the candidate with whom the i - th candidate is not ready to go to expedition, or -1, if i - th candidate is ready to go to expedition in any composition.

Now the organisers must choose which of the candidates will go to expedition. It was decided to select the expedition members so that if some candidate i and ai-1 enter there, then candidate ai does not enter there. Organisers want to choose the maximum number of expedition members.

Write a program that determines the maximum number of candidates who can be sent to expedition based on the results of a survey of candidates.


First line contains one integer n (1n300 000) - the number of candidates. The following n lines give the results of the survey, the i - th of these lines contains the result of survey of the i - th candidate, an integer ai (ai = -1 or 1ain, aii).


Print a single integer - the maximum number of candidates who can be sent to expedition.

Time limit 1 second
Memory limit 128 MiB
Input example #1
Output example #1
Input example #2
Output example #2
Source 2019 All Russia school informatics olympiad, Regional stage, Day 2, Moscow, January 28, Problem C