BoB004-D: Alchemist 2

2 secs 1024 MB
kyaneko999

問題


錬金術師である Sakky さんは以下のような錬金術を使うことができます.

  • 偶数であるような つの整数 を選び, を消滅させる代わりに整数 を生成する.

個の整数 が与えられたとき,Sakky さんは上記の錬金術を最大で何回行うことができるか答えてください.

制約


  • 入力はすべて整数

入力


入力は以下の形式で標準入力から与えられる.


出力


答えを整数で出力しなさい.

入出力例


入力例1
3
3 1 4
出力例1
2

最初に, に対して錬金術を行い を生成します.
次に,先ほど生成した と残りの に対して錬金術を行い を生成します.
この時点で残った整数は つだけであるため,これ以上錬金術を行うことはできません.

入力例2
3
1 2 3
出力例2
1

最初に, に対して錬金術を行い を生成します.
残った整数は であり積が偶数ではないため,これ以上錬金術を行うことはできません.

入力例3
5
1 7 11 13 1001
出力例3
0

どの つの数を選んでも積が偶数ではないため, 回も錬金術を行うことはできません.

提出


Go (1.14)