Fruit Crush (Get Min Fruits)

Each time, remove two fruits of different kinds; you may choose any positions and repeat this any number of times. Find the minimum number of fruits left at the end.

输入格式

The first line contains n (1..100000), and the second line contains n kind IDs (1..10⁹).

输出格式

Output a single integer, the answer.

样例 1

输入：

5
3 3 1 1 2

输出：

1

样例 2

输入：

4
1 1 1 2

输出：

2

样例 3

输入：

2
1 2

输出：

0

样例说明

Example 1: remove one 3 together with a 1, then the other 3 with another 1, leaving the 2, so 1 fruit remains. Example 2: the only 2 can remove just one 1, leaving two 1s. Example 3: the two kinds are removed together directly, leaving 0.