K. Starlight Blend
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In the alchemy chamber of the Astra ruins, Little A found $$$N$$$ starlight crystal stones. The energy value of the $$$i$$$-th crystal stone is $$$A_i$$$.

According to the ancient alchemy rule, only by combining a crystal with an odd energy value and a crystal with an even energy value can a perfect and stable 'Starlight Core' be synthesized.

Each crystal stone can only be fused once (meaning it is consumed once it is used).

Little A hopes to synthesize as many 'Starlight Core' as possible. Please help him calculate how many Starlight Cores can be synthesized with these $$$N$$$ gemstones?

Input

The first line contains an integer $$$N$$$ ($$$1 \le N \le 5 \times 10^5$$$), representing the number of gemstones.

The second line contains $$$N$$$ integers $$$A_1, A_2, \dots, A_N$$$ ($$$1 \le A_i \le 10^9$$$), representing the energy values of each crystal stone

Output

Output a single integer, indicating the maximum number of starlight cores that can be synthesized.

Examples
Input
5
1 2 3 4 5
Output
2
Input
4
2 4 6 8
Output
0
Note

For example 1

If you have 5 crystals at hand, their energies are 1, 2, 3, 4, and 5.

The odd numbers are $$$1, 3, 5$$$, and the even numbers are $$$2, 4$$$.

The points $$$(1, 2)$$$ and $$$(3, 4)$$$ can be combined. The remaining 5 cannot be paired with even crystal stones. At most, 2 cores can be synthesized.