P16817 [Lanqiao Cup 2026 National Python B] Stable Slimes

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.

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 one integer, representing the minimum number of spell casts needed to make all slimes stable.

### 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