Problem Description

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?

Input Format

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.

Output Format

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

4
1 2 2 3

1

Hint

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