Marisa Steals Reimu's Takeout

Strip away the nonsense

Because Marisa can choose an arbitrary subsequence, the order of the array does not matter at all. We only care about the counts:

$$c_0 = \#0, \qquad c_1 = \#1, \qquad c_2 = \#2.$$

An operation is just choosing some multiset of these values whose sum is divisible by $3$.

Zeros are free money

A single $0$ already has sum $0$, so each zero can be removed in its own operation.

Also, putting a zero into a larger operation is never useful. If an operation removes some zeros plus other elements, split those zeros off into separate operations. That only increases the count. So zeros contribute exactly

$$c_0$$

operations.

Now ignore zeros.

What can we do with $1$'s and $2$'s?

A $1$ and a $2$ together sum to $3$, so every pair $(1,2)$ gives one operation.

If one type is left over, say only $1$'s remain, then the only way to make a sum divisible by $3$ is to take triples:

$$1+1+1=3.$$

Similarly,

$$2+2+2=6.$$

So the greedy construction is:

1. Make $\min(c_1,c_2)$ pairs $(1,2)$.
2. Let $|c_1-c_2|$ be the leftover count of one residue.
3. Every $3$ leftovers make one more operation.

This gives

$$\min(c_1,c_2)+\left\lfloor\frac{|c_1-c_2|}{3}\right\rfloor.$$

Adding zeros:

$$\boxed{c_0+\min(c_1,c_2)+\left\lfloor\frac{|c_1-c_2|}{3}\right\rfloor}$$

Why this is optimal

Assume $c_1 \le c_2$. We prove no strategy can beat

$$c_1+\left\lfloor\frac{c_2-c_1}{3}\right\rfloor.$$

Give each $1$ a potential of $2$, and each $2$ a potential of $1$. Total potential is

$$2c_1+c_2.$$

Consider any valid non-empty operation using $x$ ones and $y$ twos. Its sum is divisible by $3$. Such a group must have potential

$$2x+y \ge 3.$$

Indeed, the valid smallest groups are $(1,2)$ and $(2,2,2)$ under this weighting, both costing $3$ potential; triples of ones cost even more.

Therefore every operation consumes at least $3$ potential, so the number of nonzero operations is at most

$$\left\lfloor\frac{2c_1+c_2}{3}\right\rfloor = c_1+\left\lfloor\frac{c_2-c_1}{3}\right\rfloor.$$

Our greedy construction reaches exactly that, so it is optimal. The case $c_2 \le c_1$ is symmetric.

Complexity

For each test case, we just count values and apply the formula.

$$O(n) \text{ time}, \qquad O(1) \text{ memory}.$$