题解

题面描述

给定一个长度为 $n$ 的数组 $a$。
每次操作可以选择任意的下标 $i,j$（$1 \leq i,j \leq n$），同时进行如下变换：

• 将 $a_i$ 变为 $a_i \times a_j$
• 将 $a_j$ 变为 $\operatorname{lcm}(a_i,a_j)$

题目内容

小红有一个长度为$n$的数组$a$。

她每次可以选定任意的$i,j(1≤i,j≤n)$,然后将$a_i→a_i×a_j$,

$a_j→lcm(a_i,a_j)$,两个操作是同时进行的，没有先后顺序。

小红想知道，把整个数组变成全部都是偶数元素的最少操作次数，若始终无法全变成偶数，输出$-1$。

输入描述

第一行输入一个正整数$n(1≤n≤10^5)$,表示数组a的长度。

第二行输入$n$个正整数,表示数组$a$,其中$1≤a_i≤10^9$

输出描述

输出一个整数，表示把整个数组变成全部都是偶数元素的最少操作次数，若始终无法全变成偶数，输出$-1$。

样例1

输入

2
1 2

输出

1

样例2

输入

2
1 1

输出

-1