Problem Description

Xiao Lan raises $N$ slimes. The initial weight of the $i$-th slime is $a_i$.

It is known that a slime whose weight is not a multiple of $3$ is in a stable state, while a slime whose weight is a multiple of $3$ is in an unstable state. To make all slimes stable, Xiao Lan can cast a splitting spell.

Each time he casts the spell, Xiao Lan may choose a value $W$ that is divisible by $3$. When the spell takes effect, all slimes whose current weight is exactly $W$ will split at the same time. Each such slime becomes three slimes of weight $W/3$.

Now, please compute the minimum number of spells Xiao Lan needs to cast so that all slimes become stable.

Input Format

The first line contains an integer $N$, representing the initial number of slimes.

The second line contains $N$ positive integers $a_1, a_2, \dots, a_N$, representing the initial weights of the slimes.

Output Format

Output one integer, representing the minimum number of spell casts needed to make all slimes stable.

5
18 7 9 6 3

4

Hint

Sample Explanation

The initial weight sequence is: $[18, 7, 9, 6, 3]$.

1. Choose $W = 18$: the only $18$ in the sequence splits, and the sequence becomes $[6, 6, 6, 7, 9, 6, 3]$.
2. Choose $W = 9$: the only $9$ in the sequence splits, and the sequence becomes $[6, 6, 6, 7, 3, 3, 3, 6, 3]$.
3. Choose $W = 6$: now there are four $6$'s in the sequence, and they all split at the same time into $2$ (reaching a stable state), and the sequence becomes $[2, 2, 2, 2, 2, 2, 2, 2, 7, 3, 3, 3, 2, 2, 2, 3]$.
4. Choose $W = 3$: now all $3$'s in the sequence split at the same time into $1$ (reaching a stable state).

After $4$ spells, none of the slimes' weights is divisible by $3$, and all of them have reached a stable state.

Constraints

For $30\%$ of the testdata: $1 \le N \le 1000$, $1 \le a_i \le 10^5$.

For all testdata: $1 \le N \le 10^6$, $1 \le a_i \le 10^9$.

Translated by ChatGPT 5