Yasmar Nodrog is baking cookies to share between himself and his friend Larry the magical panda! Over the past few days, Yasmar baked $N$ batches of cookies, with the $i$-th batch consisting of $a_i$ cookies. Yasmar, being the good friend he is, will always share his cookies fairly with Larry. More specifically, Yasmar will repeat the following process until he cannot repeat it anymore:

First he will select $2$ batches of cookies to share with Larry. Then he will divide the cookies evenly between himself and Larry and remove all of the cookies from the chosen batches. Note that both Yasmar and Larry have extremely high standards and will only accept full cookies, meaning that it must be possible to divide the cookies in the chosen batches evenly.

Help Yasmar find the maximum number of times he can repeat this procedure!

Constraints

$1\le N\le 2\times {10}^5$

$1\le a_i\le {10}^9$

Subtask 1 [25%]

$a_i=2$

Subtask 2 [25%]

$a_i=1$

Subtask 3 [25%]

$1\le N\le 3$

Subtask 4 [25%]

No additional constraints.

Input Specification

The first line of input will consist of a single integer $N$.

The next and final line of input will contain $N$ space-separated integers, denoting the number of cookies in each batch.

Output Specification

Output a single integer representing the maximum number of times Yamsar can repeat the procedure.

Sample Input 1

8
1 2 3 4 5 6 7 11

Sample Output 1

3

Explanation for Sample Output 1

A possible ordering of length $3$ is $(1,3),(5,7),(2,4)$, where $(x,y)$ means that you choose the cookie batches with $x$ cookies and $y$ cookies. It can be proven that you cannot perform the operation more than $3$ times.

Sample Input 2

4
1 2 3 4

Sample Output 2

2