P10693 [SNCPC2024] Changing Seats

The Tree Kingdom is preparing to hold a grand celebration. As the celebration designer of the Tree Kingdom, Shirost plans to invite $n$ guests to attend. There are $2n$ seats prepared for the celebration. **Each seat can have at most one person, and each person must sit in exactly one seat**. Shirost’s initial plan is to arrange guest $i$ to sit in seat $i$. However, the president investigated the wishes of these $n$ guests: guest $i$’s preferred seat is seat $a_i$. But unless they can sit in their preferred seat, they are only willing to sit in their original seat. The president hopes Shirost can modify the plan so that as many guests as possible can sit in their preferred seats. Formally, you need to find an array $b_i$ of length $n$ ($1 \leq i \leq n, 1 \leq b_i \leq 2n$) such that $\forall i \neq j, b_i \neq b_j$ and $\forall i, b_i=i$ or $b_i=a_i$, and maximize the number of indices with $b_i = a_i$. You only need to output this maximum number.

The first line contains an integer $n$ ($1 \leq n \leq 10^{5}$), representing the total number of people. The second line contains $n$ integers $a_i$ ($1 \leq a_i \leq 2n$), separated by spaces, representing each person’s preferred seat.

Output only one line with one integer, representing the maximum number of guests who can sit in their preferred seats.

For the first sample, everyone can switch to their preferred seat. Translated by ChatGPT 5