题目内容

魔法师有 $n$ 颗魔法水晶，第 $i$ 颗的魔力值为 $a_i$。她可以反复施展一种共鸣术：选定两个下标 $i$ 和 $j$（$1 \le i, j \le n$），同时将 $a_i$ 变为 $a_i \times a_j$，将 $a_j$ 变为 $\operatorname{lcm}(a_i, a_j)$。她希望经过若干次操作后，所有水晶的魔力值都能被 $2$ 整除。请求出所需的最少操作次数；如果无法达成目标，请输出 $-1$。

数据范围：水晶数量 $n$ 满足 $1 \le n \le 10^5$，每颗水晶的初始魔力值 $a_i$ 满足 $1 \le a_i \le 10^9$。

输入描述

第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示水晶的数量。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$），表示每颗水晶的初始魔力值，相邻整数间以空格分隔。

输出描述