除以 2 或 3

题目描述

给你一个正整数序列 $A=(a_1,a_2,\ldots,a_N)$。

你可以任意次(可能为 0 次)选择并执行以下操作之一。

选择满足 $1 \leq i \leq N$ 且 $a_i$ 是 $2$ 的倍数的整数 $i$,将 $a_i$ 替换为 $\frac{a_i}{2}$。

选择满足 $1 \leq i \leq N$ 且 $a_i$ 是 $3$ 的倍数的整数 $i$,将 $a_i$ 替换为 $\frac{a_i}{3}$。

你的目标是使 $A$ 满足 $a_1=a_2=\ldots=a_N$。

求达成目标所需执行操作的最小总次数。如果无法达成目标,输出 $-1$。

输入格式

输入按以下格式从标准输入给出:

$N$
$a_1$ $a_2$ $\ldots$ $a_N$

输出格式

输出答案。

样例

3
1 4 3

3

下面是达成目标的一种方式,需要三次操作,这是最小的次数。

选择满足 $a_i$ 是 $2$ 的倍数的整数 $i=2$,将 $a_2$ 替换为 $\frac{a_2}{2}$。$A$ 变为 $(1,2,3)$。

选择满足 $a_i$ 是 $2$ 的倍数的整数 $i=2$,将 $a_2$ 替换为 $\frac{a_2}{2}$。$A$ 变为 $(1,1,3)$。

选择满足 $a_i$ 是 $3$ 的倍数的整数 $i=3$,将 $a_3$ 替换为 $\frac{a_3}{3}$。$A$ 变为 $(1,1,1)$。

3
2 7 6

-1

无法达成目标。

6
1 1 1 1 1 1

0

数据范围

• $2 \leq N \leq 1000$
• $1 \leq a_i \leq 10^9$
• 输入中的所有值均为整数。