A: Union Ball

Problem Statement

There are N balls in a box. The i-th ball is labeled with a positive integer A_i.

You can interact with balls in the box by taking actions under the following rules:

• If integers on balls in the box are all odd or all even, you cannot take actions anymore.
• Otherwise, you select arbitrary two balls in the box and remove them from the box. Then, you generate a new ball labeled with the sum of the integers on the two balls and put it into the box.

For given balls, what is the maximum number of actions you can take under the above rules?

Input

N
A_1 A_2 ... A_N

• The first line gives an integer N representing the initial number of balls in a box.
• The second line contains N integers, the i-th of which is the integer on the i-th ball.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq 10^9
• Inputs consist only of integers.

Output

Output the maximum number of actions you can take in one line.

Sample Input 1

3
4 5 6

Output for Sample Input 1

2

First, you select and remove balls labeled with 4 and 5, respectively, and add a ball labeled with 9. Next, you select and remove balls labeled with 6 and 9, respectively, and add a ball labeled with 15. Now, the balls in the box only have odd numbers. So you cannot take any actions anymore. The number of actions you took is two, and there is no way to achieve three actions or more. Thus the maximum is two and the series of the above actions is one of the optimal ways.

Sample Input 2

4
4 2 4 2

Output for Sample Input 2

0

You cannot take any actions in this case.