Minimum Cost to Move Chips

You are given a list of positions of chips on a number line. In one move, you can move a chip by 2 units to the left or right with no cost. Alternatively, you can move a chip by 1 unit to the left or right with a cost of 1.

Your task is to determine the minimum cost required to move all the chips to the same position.

Formally, let the positions be given by an array \(p_1, p_2, \dots, p_n\). The cost to move a chip from position \(p_i\) to \(x\) is defined as:

\[ cost(p_i, x) = \begin{cases} 0, & \text{if } |p_i - x| \text{ is even},\\ 1, & \text{if } |p_i - x| \text{ is odd}. \end{cases} \]

Thus, the total cost is \(\sum_{i=1}^n cost(p_i, x)\) and you are to minimize this over all possible \(x\).

inputFormat

The first line contains an integer \(n\) \((1 \leq n \leq 10^5)\) representing the number of chips.

The second line contains \(n\) integers \(p_1, p_2, \dots, p_n\) \((1 \leq p_i \leq 10^9)\) where each number represents the position of a chip.

outputFormat

Output a single integer that represents the minimum total cost required to move all the chips to the same position.

## sample

3
1 2 3

1

</p>