Problem Statement

There are $N$ pieces at integer coordinates on a one-dimensional number line.
The initial coordinates of the pieces are pairwise distinct and are $X_1,X_2,\ldots,X_N$.
In $1$ operation, you can move $1$ piece: if its current coordinate is $x$, it can move to $x+2$ or $x-2$.
However, such a move is not allowed if there is already a piece at the destination. Also, if a piece jumps over another piece while moving, both the jumping piece and the piece jumped over disappear.
You want to minimize the number of pieces.
Write a program that finds the minimum possible number of pieces remaining at the end, given that you may perform any number of operations.

Input

$N$
$X_1$ $X_2$ $\cdots$ $X_N$

$1 \leq N \leq 10^5$
$-10^9 \leq X_k \leq 10^9$

Output

Output the minimum number of remaining pieces on $1$ line.
Print a newline at the end.

Sample

4
1 2 4 3

0

10
-746 0 11 98 1 14 998 123 837 15

0

5
1000000000 -1000000000 0 987654321 -123456789

1