题目描述

小蓝养了 $N$ 只史莱姆，其中第 $i$ 只史莱姆的初始体重为 $a_i$。

已知体重不为 $3$ 的倍数的史莱姆处于稳定状态，体重为 $3$ 的倍数的史莱姆则处于不稳定状态。为了让所有的史莱姆都达到稳定状态，小蓝可以施放分裂魔法。

每次施法时，小蓝可以指定一个能被 $3$ 整除的数值 $W$。随着魔法生效，当前所有体重恰好为 $W$ 的史莱姆会同时发生分裂，每只史莱姆都会变成三只体重为 $W/3$ 的史莱姆。

现在，请你计算小蓝最少需要施放多少次魔法，才能使所有的史莱姆都达到稳定状态。

输入格式

第一行包含一个整数 $N$，表示史莱姆的初始数量。

第二行包含 $N$ 个正整数 $a_1, a_2, \dots, a_N$，依次表示每只史莱姆的初始体重。

输出格式

输出一个整数，代表使所有史莱姆都达到稳定状态所需的最少魔法施放次数。

5
18 7 9 6 3

4

提示

【样例说明】

初始体重序列为：$[18, 7, 9, 6, 3]$。

1. 指定数值 $W = 18$：序列中唯一的 $18$ 发生分裂，序列变为 $[6, 6, 6, 7, 9, 6, 3]$；
2. 指定数值 $W = 9$：序列中唯一的 $9$ 发生分裂，序列变为 $[6, 6, 6, 7, 3, 3, 3, 6, 3]$；
3. 指定数值 $W = 6$：此时序列中共有四个 $6$，它们同时分裂为 $2$（达到稳定状态），序列变为 $[2, 2, 2, 2, 2, 2, 2, 2, 7, 3, 3, 3, 2, 2, 2, 3]$；
4. 指定数值 $W = 3$：此时序列中所有的 $3$ 同时分裂为 $1$（达到稳定状态）。

经过 $4$ 次施法后，所有史莱姆的体重均不能被 $3$ 整除，全部达到了稳定状态。

【评测用例规模与约定】

对于 $30\%$ 的评测用例：$1 \le N \le 1000$，$1 \le a_i \le 10^5$；

对于所有评测用例：$1 \le N \le 10^6$，$1 \le a_i \le 10^9$。