#P10933. Maximizing the Selection of World Elements

    ID: 12981 Type: Default 1000ms 256MiB

Maximizing the Selection of World Elements

Maximizing the Selection of World Elements

God possesses NN types of world elements. Each element can restrict exactly one other type of element. For each ii (1iN1 \le i \le N), the element ii can restrict element A[i]A[i]. God plans to deploy a subset of these elements into a new space to construct a world. However, to ensure peace and tranquility, he requires that for every deployed (selected) world element, at least one world element that can restrict it is not deployed. In other words, if an element jj is deployed, then there must exist at least one index ii with A[i]=jA[i] = j such that the iith element is not deployed.

Your task is to help God maximize the number of deployed world elements. Formally, let SS be the set of deployed elements. The condition is that for every jSj \in S, there exists some ii with A[i]=jA[i] = j and iSi \notin S. Find the maximum possible size of SS.

inputFormat

The first line contains a single integer $N$ ($1 \le N \le 10^5$), the number of world elements.

The second line contains $N$ integers $A[1], A[2], \dots, A[N]$ ($1 \le A[i] \le N$, and it is allowed that $A[i]=i$ but note that each element restricts exactly one other element). These numbers describe the restriction relationship: element $i$ can restrict element $A[i]$.

outputFormat

Output a single integer: the maximum number of world elements that can be deployed while satisfying the condition that for every deployed element $j$, there exists at least one element $i$ (with $A[i] = j$) which is not deployed.

sample

3
2 3 2
1