P9421 [Lanqiao Cup 2023 National B] Class Activity

Xiaoming’s teacher is preparing to organize a class activity. There are $n$ students in the class ($n$ is even). The teacher wants to split all students into groups, with two students per group. To be fair, the teacher randomly assigns each student a positive integer within $n$ as their id. The id of the $i$-th student is $a_i$. The teacher hopes to change the ids of some students so that for any student $i$, there exists exactly one other student $j$ whose id is the same as theirs ($a_i = a_j$). How many students’ ids does the teacher need to change at minimum?

The input consists of $2$ lines. The first line contains a positive integer $n$. The second line contains $n$ integers $a_1, a_2, \cdots, a_n$ separated by spaces.

The output consists of $1$ line, an integer.

### Sample Explanation You only need to change $a_1$ to $3$, or change $a_4$ to $1$. ### Constraints - For $20\%$ of the testdata, it is guaranteed that $n \le 10^3$. - For $100\%$ of the testdata, it is guaranteed that $n \le 10^5$. The 14th Lanqiao Cup Software Contest Finals, C/C++ University Group B, Problem C. Translated by ChatGPT 5