Let's Play Crush Fruit Together :)

In each step, pick one fruit from each of two different types and delete both; they do not need to be adjacent. You cannot delete a pair of the same type. Find the minimum number of fruits left.

输入格式

The first line contains n and the second line contains n type integers. The original bounds are 1≤n≤100000, 1≤type≤10^9.

输出格式

Output a single integer, the answer.

样例 1

输入：

5
3 3 1 1 2

输出：

1

样例 2

输入：

4
1 2 5 6

输出：

0

样例 3

输入：

4
7 7 7 1

输出：

2

样例说明

The outputs of the three public examples are 1; 0; and 2, checked by independent enumeration or direct simulation.