102763: [AtCoder]ABC276 D - Divide by 2 or 3

Problem Statement

You are given a sequence of positive integers: $A=(a_1,a_2,\ldots,a_N)$.
You can choose and perform one of the following operations any number of times, possibly zero.

• Choose an integer $i$ such that $1 \leq i \leq N$ and $a_i$ is a multiple of $2$, and replace $a_i$ with $\frac{a_i}{2}$.
• Choose an integer $i$ such that $1 \leq i \leq N$ and $a_i$ is a multiple of $3$, and replace $a_i$ with $\frac{a_i}{3}$.

Your objective is to make $A$ satisfy $a_1=a_2=\ldots=a_N$.
Find the minimum total number of times you need to perform an operation to achieve the objective. If there is no way to achieve the objective, print -1 instead.

Constraints

• $2 \leq N \leq 1000$
• $1 \leq a_i \leq 10^9$
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

3
1 4 3

Sample Output 1

3

Here is a way to achieve the objective in three operations, which is the minimum needed.

• Choose an integer $i=2$ such that $a_i$ is a multiple of $2$, and replace $a_2$ with $\frac{a_2}{2}$. $A$ becomes $(1,2,3)$.
• Choose an integer $i=2$ such that $a_i$ is a multiple of $2$, and replace $a_2$ with $\frac{a_2}{2}$. $A$ becomes $(1,1,3)$.
• Choose an integer $i=3$ such that $a_i$ is a multiple of $3$, and replace $a_3$ with $\frac{a_3}{3}$. $A$ becomes $(1,1,1)$.

Sample Input 2

3
2 7 6

Sample Output 2

-1

There is no way to achieve the objective.

Sample Input 3

6
1 1 1 1 1 1

Sample Output 3

0

问题描述

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

• 你可以选择并执行以下任意多次操作，可能为零次。
• 选择一个满足$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。

约束

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

输入

输入以标准输入的以下格式给出：

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

输出

打印答案。

样例输入1

3
1 4 3

样例输出1

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)$。

样例输入2

3
2 7 6

样例输出2

-1

没有实现目标的方法。

样例输入3

6
1 1 1 1 1 1

样例输出3

0