Pair Formation Minimization

There are n students (where n is an even integer) with randomly assigned IDs. The ID of the i-th student is given by a_i and satisfies \(1 \le a_i \le n\). The teacher wishes to rearrange the IDs by modifying as few students as possible such that for every student \(i\) there exists exactly one other student \(j\) (with \(i \neq j\)) for which \(a_i = a_j\). In other words, after the changes each ID that appears must appear exactly twice.

Observations:

• If an ID appears more than twice (say f times with \(f > 2\)), then \(f - 2\) of those occurrences must be changed.
• If an ID appears exactly once, it is a singleton. Two singletons can be paired by modifying one of them so that both share the same ID.

Let surplus be the total number of extra occurrences from IDs with frequency greater than 2, i.e. \(\text{surplus} = \sum_{\{i: f_i>2\}} (f_i - 2)\), and let singles be the count of IDs that appear exactly once. Then the minimum number of modifications required is:

[ \text{answer} = \text{surplus} + \frac{\max(0,, singles - surplus)}{2} ]

Your task is to compute and output this minimum number.

inputFormat

The first line contains an even integer \(n\) (\(2 \le n \le 10^5\)) representing the number of students. The second line contains \(n\) space-separated integers \(a_1, a_2, \dots, a_n\) where \(1 \le a_i \le n\).

outputFormat

Output a single integer, which is the minimum number of students whose IDs need to be changed so that every ID that remains appears exactly twice.

sample

4
1 1 1 2

1