This page is still under construction.

Parts of this page are still being built. What you see may change.

Expedition

Interview

Time limit2sMemory limit512 MB

Summary
Each candidate forbids at most one other candidate; choose the largest subset where no included candidate's forbidden partner is also included.
Level

Medium6 of 10

Topics
Graph, Greedy, Dynamic programming, Tree
Solved
No attempts yet

Problem

An expedition is being planned to a neighboring star system. There are nn candidates, numbered from 1 to nn, from whom the expedition members must be chosen. The organizers want to send as many candidates as possible.

The candidates were surveyed, and each could name at most one other candidate with whom they are not willing to go on the expedition. The survey result for candidate ii is an integer aia_i, equal to the number of a candidate with whom candidate ii is not willing to go, or −1-1 if candidate ii is willing to go in any group.

Now the organizers must decide who will go on the expedition. They decided to choose the members so that if candidate ii is included and ai≠−1a_i \ne -1, then candidate aia_i is not included. The organizers want to choose the largest possible number of expedition members.

Write a program that, given the survey results, determines the maximum number of candidates that can be sent on the expedition.

Input

The first line contains the integer nn, the number of candidates (1≤n≤300 0001 \le n \le 300\,000).

The next nn lines contain the survey results; the ii-th of these lines contains the result of candidate ii, an integer aia_i (ai=−1a_i = -1 or 1≤ai≤n1 \le a_i \le n, ai≠ia_i \ne i).

Output

Output a single integer on one line: the maximum number of candidates that can be sent on the expedition.

Examples2

  1. Example 1

    Input
    4
    2
    4
    2
    1
    
    Expected output
    2
    
  2. Example 2

    Input
    3
    2
    -1
    2
    
    Expected output
    2