Alternatywne formaty: PostScript | PDF

Smok Bajtazar ma N skarbonek. Każdą skarbonkę można otworzyć jej kluczem lub rozbić młotkiem. Bajtazar powrzucał klucze do pewnych skarbonek, pamięta przy tym który do której. Bajtazar zamierza kupić samochód i potrzebuje dostać się do wszystkich skarbonek. Chce jednak zniszczyć jak najmniej z nich. Pomóż Bajtazarowi ustalić ile skarbonek musi rozbić.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia liczbę skarbonek i rozmieszczenie odpowiadających im kluczy,
• obliczy minimalną liczbę skarbonek, które trzeba rozbić, aby dostać się do wszystkich skarbonek,
• wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita N (1 <= N <= 1.000.000) - tyle skarbonek posiada smok. Skarbonki (jak również odpowiadające im klucze) są ponumerowane od 1 do N. Dalej na wejściu mamy N wierszy: w i+1-szym wierszu zapisana jest jedna liczba całkowita - numer skarbonki, w której znajduje się i-ty klucz.

Wyjście

W pierwszym i jedynym wierszu standardowego wyjścia należy zapisać jedną liczbę całkowitą - minimalną liczbę skarbonek, które trzeba rozbić, aby dostać się do wszystkich skarbonek. 

Przykład

Dla danych wejściowych:

4
2
1
2
4

prawidłową odpowiedzią jest:

2

Wersja do druku